A long art gallery has rooms. The gallery is laid out as
rows of 2 rooms
side-by-side. Doors connect all adjacent rooms (north-south and
east-west, but not diagonally). The curator has been told that
she must close off of
the rooms because of staffing cuts. Visitors must be able to
enter using at least one of the two rooms at one end of the
gallery, proceed through the gallery, and exit from at least
one of the two rooms at the other end. Therefore, the curator
must not close off any two rooms that would block passage
through the gallery. That is, the curator may not block off two
rooms in the same row or two rooms in adjacent rows that touch
diagonally. Furthermore, she has determined how much value each
room has to the general public, and now she wants to close off
those rooms that leave
the most value available to the public, without blocking
passage through the gallery.
Input
Input will consist of multiple problem instances
(galleries). Each problem instance will begin with a line
containing two integers and , where gives the number
of rows, and gives the number of rooms that must be closed off.
This is followed by
rows of two integers, giving the values of the two rooms in
that row. Each room’s value satisfies . A line containing
will follow the
last gallery.
Output
For each gallery, output the amount of value that the
general public may optimally receive, one line per gallery.
Sample Input 1 |
Sample Output 1 |
6 4
3 1
2 1
1 2
1 3
3 3
0 0
0 0
|
17
|
Sample Input 2 |
Sample Output 2 |
4 3
3 4
1 1
1 1
5 6
0 0
|
17
|
Sample Input 3 |
Sample Output 3 |
10 5
7 8
4 9
3 7
5 9
7 2
10 3
0 10
3 2
6 3
7 9
0 0
|
102
|