Narrow Art Gallery

Time limit2sMemory limit256 MB

Summary

Close exactly k rooms with no row fully closed and no diagonal closures to keep the maximum total value of open rooms.

Level: Medium5 of 10
Topics: Dynamic programming
Solved: No attempts yet

Problem

A long art gallery has $2N$ rooms. The gallery is a grid of $N$ rows and 2 columns, and rooms that touch vertically or horizontally are connected. Today the curator is told to close $k$ rooms to cut running costs.

Visitors have to enter through at least one of the two rooms in the row at one end and leave through one of the two rooms in the row at the other end. To keep that possible, the curator must not close both rooms of the same row, and must not close two rooms that touch diagonally. Closing two vertically adjacent rooms in the same column is allowed.

The curator already knows how much value each room produces when it is open to the public. Close exactly $k$ rooms under the rules above so that the total value of the open rooms is as large as possible.

Input

The input holds several galleries. The first line of each gallery has two integers $N$ and $k$ ( $3 \le N \le 200$ , $0 \le k \le N$ ), the number of rows of the gallery and the number of rooms to close. Each of the next $N$ lines has two integers, the value of the left room and the value of the right room in that row. Each room value $v$ satisfies $0 \le v \le 100$ .

A line holding 0 0 follows the last gallery and ends the input.

Output

For each gallery, print the largest total value that can stay open to the public, one per line, in input order.

Examples3

Example 1
Input
```
6 4
3 1
2 1
1 2
1 3
3 3
0 0
0 0
```
Expected output
```
17
```
Example 2
Input
```
4 3
3 4
1 1
1 1
5 6
0 0
```
Expected output
```
17
```

Example 3

Input

Expected output