Buying Paintings

Interview

Time limit14sMemory limit1024 MB

Summary

The paintings sit in a line; walking between adjacent ones costs 1 second and buying painting i costs t_i. Choose k paintings to buy, starting and ending anywhere, so the total buying plus walking time is smallest.

Level: Medium6 of 10
Topics: Dynamic programming, Array
Solved: No attempts yet

Problem

Mona has just moved and is starting to decorate. She has decided she needs exactly $k$ paintings, and she has gone to the art market to shop. Mona is very rich and does not care at all how much the paintings cost; she only wants to finish as quickly as possible.

The market sells $N$ paintings along a long street. Buying painting $i$ takes $t_i$ seconds. Walking from one painting to the next takes 1 second. Mona takes the bus there and back, so she can choose which painting she starts at and which she ends at. What is the shortest time in which Mona can buy $k$ paintings?

Input

The first line contains two integers: $N$ ( $1 \le N \le 2000$ ), the number of paintings at the market, and $k$ ( $1 \le k \le N$ ), the number of paintings Mona needs to buy.

The second line contains $N$ integers: $1 \le t_1,t_2,...t_n \le 1000$ , the number of seconds it takes to buy each painting.

Output

Print one integer, the smallest number of seconds it can take Mona to buy $k$ paintings.

Examples3

Example 1
Input
```
4 2
3 3 5 1
```
Expected output
```
6
```
Example 2
Input
```
6 4
7 4 3 10 2 5
```
Expected output
```
18
```
Example 3
Input
```
10 5
4 7 2 1 8 6 7 2 1 10
```
Expected output
```
18
```