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
package main

import (
	"fmt"
)

// https://atcoder.jp/contests/agc004/tasks/agc004_b
// 任意の色のスライムを捕まえることができるが、それにはa_i秒掛かる
// 魔法を唱えてスライムの色を次に送ることができるが、この操作はx秒掛かる
// 全ての色のスライムを揃えるのに最短で合計何秒？

// つまり、魔法の時間と捕まえる時間の組み合わせによって、直接目的の色を捕まえる方が早いか、
// 適当な色を捕まえて魔法で色を変えるのが早いかが変わる。

// 魔法を唱えたときに色が変わるのは今所持しているすべてのスライム。

func min(array []int) int {
	var min = array[0]
	for _, value := range array {
		if min > value {
			min = value
		}
	}
	return min
}

func ringrd(a []int, idx int) int {
	if idx < 0 {
		return a[len(a)-(idx*(-1))%len(a)]
	} else if idx >= len(a) {
		return a[idx%len(a)]
	} else {
		return a[idx]
	}
}

func search(a []int, i, k int) int {
	aab := make([]int, 0)
	for j := 0; j < k+1; j++ {
		aab = append(aab, ringrd(a, i-j))
	}
	//fmt.Printf("%v\n", min(aab))
	return min(aab)
}

func solve2(a []int, x int) {
	//
	// k は魔法を唱える回数。
	// b_i(k) は min{a_i, a_(i-1), ... , a_(i-k)}
	// スライム i を捕まえるのに必要な時間は k * x + b_i(k)
	// 全部のスライムを捕まえるのには k * x + sum(b_i(k), All i)

	b := make([]int, 0)
	for k := 0; k < len(a); k++ {
		bisum := 0
		for i := 0; i < len(a); i++ {
			bisum += search(a, i, k)
		}
		bisum += k * x
		b = append(b, bisum)
	}
	fmt.Printf("%v\n", min(b))
}

func solve(a []int, x int) {
	sum_t := 0
	for i, t := range a {
		if t <= x {
			// 直接捕まえた方が早い場合
			sum_t += t
		} else {
			// 別の色を捕まえて色を変えた方が早いかもしれない場合
			min := 0
			var tmp int
			for j, tt := range a {
				switch {
				case i == j:
					// 直接その色を捕まえるのにかかる時間
					// 結局これが選ばれるということは、色変換の時間より
					// 捕まえた方が早いということ
					tmp = tt
				case i > j:
					// a[j] を捕まえて、(i-j)回色を変える時間
					tmp = tt + (x * (i - j))
				case i < j:
					// a[j] を捕まえて、len(a) - (j-i) 回色を変える時間
					// 循環するので、色を変える回数は 全体の長さ - 差分
					tmp = tt + (x * (len(a) - (j - i)))
				}
				// 計算した時間が最小値を更新するかどうか
				if min == 0 || min > tmp {
					fmt.Printf("%v, %v, %v\n", i, j, tmp)
					min = tmp
				}
			}
			sum_t += min
		}

	}
	fmt.Printf("%v\n", sum_t)
}

func main() {
	var n, x int
	var a []int
	fmt.Scanf("%d %d\n", &n, &x)
	for i := 0; i < n; i++ {
		var ta int
		fmt.Scanf("%d", &ta)
		a = append(a, ta)
	}
	//solve(a, x)
	solve2(a, x)
}