Get Min Cost

At each step you may buy the leftmost or the rightmost remaining book at its original price, or buy the two different books at both ends together for pairCost. Joint purchases can be made at most k times. Find the minimum cost to buy all the books.

输入格式

The first line contains n pairCost k; the second line contains the prices. 1≤n≤100000, 1≤price,pairCost≤10^9, 1≤k≤n.

输出格式

Output a single integer, the answer.

样例 1

输入：

3 2 1
1 2 3

输出：

3

样例 2

输入：

4 1 1
100 1 1 100

输出：

3

样例 3

输入：

3 10 3
1 1 1

输出：

3

样例说明

The answers are 3, 3 and 3. In the second example the two 100s at the ends are bought together; when the discount does not pay off, you may skip it.