Q) Misty Mountain has N Stones lined up in a row. Each stone has hardness value ranging from 1 to 3. A dragon was there behind the mountain having power 'P' initially and his power is associated with each stone of mountain. If stone of ith position is broken by hammering, then power of dragon will decrease by an amount equal to hardness[i]^hardness[i-1]^hardness[i+1]) where ab = a raised to the power of b

After ith stone is broken, we re-label the positioning of stones by decreasing N by 1 i.e. [0,N-1] from left to right.You can break the stone in any order.Power required to break stone of hardness value say h is 'h' units itself.First and last stone are not allowed to break otherwise dragon will come and attack Thorin.

Find the minimum power required to kill the dragon and break the mountain. Breaking the stones is hence added to the the final power. Help Thorin !!

Input: Given an integer N number of stones and an integer 'P' power of dragon initially. Next line contains N values corresponding to hardness of the stones.

Ouput: Output the minimum power required to kill the dragon and break the mountain.

Constraints:

1 <= N <= 500 1 <= P <= 10^18 1 <= hardness value <= 3 Sample Input 4 7000 1 2 3 3 Sample Output 442