Minimum Price

N stones lying in a line

• Cost of ith stone ai units
• Type of ith stone is i
• Need to collect all N types of stones

Can perform this operation 0 or more times to change types of all stones in one step:

• Stone of type i will change to type i+1
• If type is N, change to type 1

Cost of this operation is x units

Calculate minimum price to collect all types.

N < 2000, x < 10^9

Example Input:

N=3, x=5 [50, 1, 50]
Output: 13

Explanation:

• Buy type 2 - price 1
• Perform op - price 5
• Buy type 3 - price 1
• Perform op - price 5
• Buy type 1 - price 1