시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 102 44 32 40.506%

문제

기다랗고 2N개의 방이 있는 미술관이 있다. 미술관은 세로로 N줄, 가로로 2칸의 방으로 구성된다. 위아래, 양 옆으로 붙어있는 방들은 서로 연결되어 있다. 오늘의 큐레이터는 미술관 운영진으로부터 비용 절감을 위해 k개의 방을 닫아야 한다는 통보를 받았다. 방문자들은 한쪽 끝의 두 방중 적어도 한 방에는 방문할 수 있어야 하며 다른쪽 끝의 두 방중 한 방으로 나갈 수 있어야 한다. 즉, 큐레이터는 같은 줄의 어느 두 방을 모두 닫거나 대각선으로 붙어있는 두 방을 닫아서는 안 된다는 뜻이다. 또한, 각 방들이 대중에게 공개되었을 때 얼마나 큰 가치를 지니는지를 큐레이터는 알고 있다. 큐레이터는 위 조건과 같이 방문자들의 길을 막지 않으면서 방문자들에게 공개 가능한 가치의 합을 최대로 하고 싶어한다.

그림 H.1: 샘플 인풋에 대한 최적해를 나타낸다. 회색으로 색칠된 방들을 닫아야 한다.

입력

입력은 여러 갤러리들로 구성된다. 각각의 입력은 두 정수 N과 k(3 <= N <= 200, 0 <= k < N)로 구성되며 각각 미술관의 세로길이와 닫아야 하는 방의 수를 뜻한다. 이어지는 N줄에 걸쳐 각 줄에 두 개의 정수가 입력되며, 각 줄에 존재하는 두 방의 가치를 뜻한다. 각 방의 가치 v는 0 이상 100 이하이다. 마지막 미술관의 정보 이후에는 두 개의 정수 0 0이 입력된다.

출력

각 갤러리에 대해서 한 줄에 걸쳐 대중에게 공개될 수 있는 가치의 최대합을 출력한다.

예제 입력

6 4
3 1
2 1
1 2
1 3
3 3
0 0
0 0

예제 출력

17

예제 입력 2

4 3
3 4
1 1
1 1
5 6
0 0

예제 출력 2

17

예제 입력 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

예제 출력 3

102

힌트