Snuke lives in another world, where slimes are real creatures and kept by some people. Slimes come in N colors. Those colors are conveniently numbered 1 through N. Snuke currently has no slime. His objective is to have slimes of all the colors together.

Snuke can perform the following two actions:

* Select a color i (1≤i≤N), such that he does not currently have a slime in color i, and catch a slime in color i. This action takes him a_i seconds.

* Cast a spell, which changes the color of all the slimes that he currently has. The color of a slime in color i (1≤i≤N-1) will become color i+1, and the color of a slime in color N will become color 1. This action takes him x seconds.




Find the minimum time that Snuke needs to have slimes in all N colors.

Constraints

* 2≤N≤2,000
* a_i are integers.
* 1≤a_i≤10^9
* x is an integer.
* 1≤x≤10^9

Input

The input is given from Standard Input in the following format:


N x
a_1 a_2 ... a_N


Output

Find the minimum time that Snuke needs to have slimes in all N colors.

Examples

Input

2 10
1 100


Output

12


Input

3 10
100 1 100


Output

23


Input

4 10
1 2 3 4


Output

10
require "pp"
def sget; gets.chomp; end
def iget; sget.to_i; end
def saget; gets.chomp.split; end
def iaget; saget.map {|a| a.to_i }; end

N, x = iaget
a = iaget

target_sum = 0
max_magic = 0

for i in (0..N-1)
    min_cost = nil
    target = nil
    dist = nil
    j = i + 1
    for d in (0..N-1)
        j -= 1
        j = N - 1 if j < 0
        cost = d * x + a[j]
        if min_cost.nil? || cost < min_cost
            min_cost = cost
            target = j
            dist = d
        end
    end
    # puts "node %d (min_cost = %d, target = %d, dist = %d)" % [i, min_cost, target, dist]
    target_sum += a[target]
    max_magic = max_magic < dist ? dist : max_magic
end

puts max_magic * x + target_sum
