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
N,X=gets.split.map(&:to_i)
as=gets.split.map(&:to_i)

m = as.min
mi = as.index(m)

states = Array.new(N, false)

heads=[]
total=0
i=mi
states[i]=true
heads.push(i)
total += as[i]


i=mi+1
begin
    if as[i]<m+X
        states[i]=true
        total += as[i]
        heads.push(i)
    end
    i = (i+1)%N
end while i!=mi

    #puts "test0:heads=#{heads.join(',')}"
    #puts "test0:states=#{states.join(',')}"
while states.include?(false)
    nextstates = states.clone

    (0...N).each{|i|
        if states[i]==true
            nexti = (i+1)%N
           # puts "i=#{i} states[i]=#{states[i]} nexti=#{nexti}, states[nexti]=#{states[nexti]}"
            if states[(i+1)%N]!=true
                nextstates[(i+1)%N]=true
            elsif heads.include?(nexti)
                headi = heads.index(nexti)
                headprevi = (headi-1+heads.size)%heads.size
                if as[nexti] < as[heads[headprevi]]
                    heads.delete_at(heads[headprevi])
                else
                    heads.delete_at(nexti)
                end
            end
        end
    }
    states=nextstates
    #puts "heads=#{heads.join(',')}"
    total += X
    if heads.size>0
        total += heads.map{|i| as[i]}.inject(&:+)
    end
end
puts total
exit 0


=begin
total+=m
i=mi+1
begin
    total += [m+X, As[i]].min   
    i = (i+1)%N
end while i!=mi
puts total
=end
