Minimum Weekly Input (Planning Campaingns :)

Split all activities, in their original order, into exactly weeks non-empty contiguous groups, each scheduled in its own week; the effort of a week equals the maximum effort of the activities in its group. Find the minimum total effort over all weeks.

输入格式

The first line contains n weeks and the second line contains the effort array. The original bounds are 1≤n≤300, 1≤weeks≤n, 1≤cost[i]≤100000.

输出格式

Output a single integer, the answer.

样例 1

输入：

5 3
1000 500 2000 8000 1500

输出：

9500

样例 2

输入：

3 3
1 2 3

输出：

6

样例 3

输入：

3 1
5 1 4

输出：

5

样例说明

The answers are 9500, 6 and 5. The number of weeks must be exactly as given; no week can be empty, and activities cannot be reordered.