X 만들기

초깃값이 $0$인 정수 $p$가 있다. 당신은 다음 $K+1$가지 연산을 원하는 만큼 사용할 수 있다.

• $1 \leq i \leq K$인 정수 $i$를 골라 $p$를 $p+i$로 바꾼다. 이 연산의 비용은 $A_i$이다.
• $p$를 $2p$로 바꾼다. 이 연산의 비용은 $B$이다.

연산을 여러 번 수행하여 $p$를 주어진 양의 정수 $X$로 만들 때 필요한 비용의 최솟값을 구하여라.

입력은 다음과 같은 형식으로 주어진다.

$K\ X$ $A_1\ A_2\ \cdots\ A_K$ $B$

$p$를 $X$로 만들기 위해 필요한 비용의 최솟값을 출력한다.

• $1 \leq K \leq 100$.
• $1 \leq X \leq 10^{18}$.
• $1 \leq A_i \leq 10^9$ ($1 \leq i \leq K$).
• $1 \leq B \leq 10^9$.
• 입력으로 주어지는 모든 값은 정수이다.