시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 200 84 54 36.486%

문제

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

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

입력

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

출력

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

예제 입력 1

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

예제 출력 1

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
W3sicHJvYmxlbV9pZCI6IjEwNDc2IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjODgxXHVjNzQwIFx1YmJmOFx1YzIyMFx1YzgwNFx1YzJkY1x1YWQwMCIsImRlc2NyaXB0aW9uIjoiPHA+XHVhZTMwXHViMmU0XHViNzk3XHVhY2UwIDJOXHVhYzFjXHVjNzU4IFx1YmMyOVx1Yzc3NCBcdWM3ODhcdWIyOTQgXHViYmY4XHVjMjIwXHVhZDAwXHVjNzc0IFx1Yzc4OFx1YjJlNC4gXHViYmY4XHVjMjIwXHVhZDAwXHVjNzQwIFx1YzEzOFx1Yjg1Y1x1Yjg1YyBOXHVjOTA0LCBcdWFjMDBcdWI4NWNcdWI4NWMgMlx1Y2U3OFx1Yzc1OCBcdWJjMjlcdWM3M2NcdWI4NWMgXHVhZDZjXHVjMTMxXHViNDFjXHViMmU0LiBcdWM3MDRcdWM1NDRcdWI3OTgsIFx1YzU5MSBcdWM2MDZcdWM3M2NcdWI4NWMgXHViZDk5XHVjNWI0XHVjNzg4XHViMjk0IFx1YmMyOVx1YjRlNFx1Yzc0MCBcdWMxMWNcdWI4NWMgXHVjNWYwXHVhY2IwXHViNDE4XHVjNWI0IFx1Yzc4OFx1YjJlNC4gXHVjNjI0XHViMjk4XHVjNzU4IFx1ZDA1MFx1YjgwOFx1Yzc3NFx1ZDEzMFx1YjI5NCBcdWJiZjhcdWMyMjBcdWFkMDAgXHVjNmI0XHVjNjAxXHVjOWM0XHVjNzNjXHViODVjXHViZDgwXHVkMTMwIFx1YmU0NFx1YzZhOSBcdWM4MDhcdWFjMTBcdWM3NDQgXHVjNzA0XHVkNTc0IGtcdWFjMWNcdWM3NTggXHViYzI5XHVjNzQ0IFx1YjJlYlx1YzU0NFx1YzU3YyBcdWQ1NWNcdWIyZTRcdWIyOTQgXHVkMWI1XHViY2Y0XHViOTdjIFx1YmMxYlx1YzU1OFx1YjJlNC4gXHViYzI5XHViYjM4XHVjNzkwXHViNGU0XHVjNzQwIFx1ZDU1Y1x1Y2FiZCBcdWIwNWRcdWM3NTggXHViNDUwIFx1YmMyOVx1YzkxMSBcdWM4MDFcdWM1YjRcdWIzYzQgXHVkNTVjIFx1YmMyOVx1YzVkMFx1YjI5NCBcdWJjMjlcdWJiMzhcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YzViNFx1YzU3YyBcdWQ1NThcdWJhNzAgXHViMmU0XHViOTc4XHVjYWJkIFx1YjA1ZFx1Yzc1OCBcdWI0NTAgXHViYzI5XHVjOTExIFx1ZDU1YyBcdWJjMjlcdWM3M2NcdWI4NWMgXHViMDk4XHVhYzA4IFx1YzIxOCBcdWM3ODhcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWM5ODksIFx1ZDA1MFx1YjgwOFx1Yzc3NFx1ZDEzMFx1YjI5NCBcdWFjMTlcdWM3NDAgXHVjOTA0XHVjNzU4IFx1YzViNFx1YjI5MCBcdWI0NTAgXHViYzI5XHVjNzQ0IFx1YmFhOFx1YjQ1MCBcdWIyZWJcdWFjNzBcdWIwOTggXHViMzAwXHVhYzAxXHVjMTIwXHVjNzNjXHViODVjIFx1YmQ5OVx1YzViNFx1Yzc4OFx1YjI5NCBcdWI0NTAgXHViYzI5XHVjNzQ0IFx1YjJlYlx1YzU0NFx1YzExY1x1YjI5NCBcdWM1NDggXHViNDFjXHViMmU0XHViMjk0IFx1YjczYlx1Yzc3NFx1YjJlNC4gXHViNjEwXHVkNTVjLCBcdWFjMDEgXHViYzI5XHViNGU0XHVjNzc0IFx1YjMwMFx1YzkxMVx1YzVkMFx1YWM4YyBcdWFjZjVcdWFjMWNcdWI0MThcdWM1YzhcdWM3NDQgXHViNTRjIFx1YzViY1x1YjljOFx1YjA5OCBcdWQwNzAgXHVhYzAwXHVjZTU4XHViOTdjIFx1YzljMFx1YjJjOFx1YjI5NFx1YzljMFx1Yjk3YyBcdWQwNTBcdWI4MDhcdWM3NzRcdWQxMzBcdWIyOTQgXHVjNTRjXHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHVkMDUwXHViODA4XHVjNzc0XHVkMTMwXHViMjk0IFx1YzcwNCBcdWM4NzBcdWFjNzRcdWFjZmMgXHVhYzE5XHVjNzc0IFx1YmMyOVx1YmIzOFx1Yzc5MFx1YjRlNFx1Yzc1OCBcdWFlMzhcdWM3NDQgXHViOWM5XHVjOWMwIFx1YzU0YVx1YzczY1x1YmE3NFx1YzExYyBcdWJjMjlcdWJiMzhcdWM3OTBcdWI0ZTRcdWM1ZDBcdWFjOGMgXHVhY2Y1XHVhYzFjIFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWFjMDBcdWNlNThcdWM3NTggXHVkNTY5XHVjNzQ0IFx1Y2Q1Y1x1YjMwMFx1Yjg1YyBcdWQ1NThcdWFjZTAgXHVjMmY2XHVjNWI0XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246Y2VudGVyXCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzMlwvZ2FsbGVyeS5wbmdcIiBzdHlsZT1cImhlaWdodDozNTFweDsgd2lkdGg6OTBweFwiIFwvPjxcL3A+XHJcblxyXG48cD5cdWFkZjhcdWI5YmMgSC4xOiBcdWMwZDhcdWQ1MGMgXHVjNzc4XHVkNDhiXHVjNWQwIFx1YjMwMFx1ZDU1YyBcdWNkNWNcdWM4MDFcdWQ1NzRcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LiBcdWQ2OGNcdWMwYzlcdWM3M2NcdWI4NWMgXHVjMGM5XHVjZTYwXHViNDFjIFx1YmMyOVx1YjRlNFx1Yzc0NCBcdWIyZWJcdWM1NDRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1YzVlY1x1YjdlYyBcdWFjMjRcdWI3ZWNcdWI5YWNcdWI0ZTRcdWI4NWMgXHVhZDZjXHVjMTMxXHViNDFjXHViMmU0LiBcdWFjMDFcdWFjMDFcdWM3NTggXHVjNzg1XHViODI1XHVjNzQwIFx1YjQ1MCBcdWM4MTVcdWMyMTggTlx1YWNmYyBrKDMgJmx0Oz0gTiAmbHQ7PSAyMDAsIDAgJmx0Oz0gayAmbHQ7IE4pXHViODVjIFx1YWQ2Y1x1YzEzMVx1YjQxOFx1YmE3MCBcdWFjMDFcdWFjMDEgXHViYmY4XHVjMjIwXHVhZDAwXHVjNzU4IFx1YzEzOFx1Yjg1Y1x1YWUzOFx1Yzc3NFx1YzY0MCBcdWIyZWJcdWM1NDRcdWM1N2MgXHVkNTU4XHViMjk0IFx1YmMyOVx1Yzc1OCBcdWMyMThcdWI5N2MgXHViNzNiXHVkNTVjXHViMmU0LiBcdWM3NzRcdWM1YjRcdWM5YzBcdWIyOTQgTlx1YzkwNFx1YzVkMCBcdWFjNzhcdWNjZDAgXHVhYzAxIFx1YzkwNFx1YzVkMCBcdWI0NTAgXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOFx1YWMwMCBcdWM3ODVcdWI4MjVcdWI0MThcdWJhNzAsIFx1YWMwMSBcdWM5MDRcdWM1ZDAgXHVjODc0XHVjN2FjXHVkNTU4XHViMjk0IFx1YjQ1MCBcdWJjMjlcdWM3NTggXHVhYzAwXHVjZTU4XHViOTdjIFx1YjczYlx1ZDU1Y1x1YjJlNC4gXHVhYzAxIFx1YmMyOVx1Yzc1OCBcdWFjMDBcdWNlNTggdlx1YjI5NCAwIFx1Yzc3NFx1YzBjMSAxMDAgXHVjNzc0XHVkNTU4XHVjNzc0XHViMmU0LiBcdWI5YzhcdWM5YzBcdWI5YzkgXHViYmY4XHVjMjIwXHVhZDAwXHVjNzU4IFx1YzgxNVx1YmNmNCBcdWM3NzRcdWQ2YzRcdWM1ZDBcdWIyOTQgXHViNDUwIFx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMyMTggMCAwXHVjNzc0IFx1Yzc4NVx1YjgyNVx1YjQxY1x1YjJlNC5cclxuPFwvcD4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVhYzI0XHViN2VjXHViOWFjXHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYyBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1YWM3OFx1Y2NkMCBcdWIzMDBcdWM5MTFcdWM1ZDBcdWFjOGMgXHVhY2Y1XHVhYzFjXHViNDIwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhYzAwXHVjZTU4XHVjNzU4IFx1Y2Q1Y1x1YjMwMFx1ZDU2OVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuXHJcbjxcL3A+IiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTA0NzYiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJOYXJyb3cgQXJ0IEdhbGxlcnkiLCJkZXNjcmlwdGlvbiI6IjxwPkEgbG9uZyBhcnQgZ2FsbGVyeSBoYXMgMk4gcm9vbXMuIFRoZSBnYWxsZXJ5IGlzIGxhaWQgb3V0IGFzIE4gcm93cyBvZiAyIHJvb21zIHNpZGUtYnktc2lkZS4gRG9vcnMgY29ubmVjdCBhbGwgYWRqYWNlbnQgcm9vbXMgKG5vcnRoLXNvdXRoIGFuZCBlYXN0LXdlc3QsIGJ1dCBub3QgZGlhZ29uYWxseSkuIFRoZSBjdXJhdG9yIGhhcyBiZWVuIHRvbGQgdGhhdCBzaGUgbXVzdCBjbG9zZSBvZmYgayBvZiB0aGUgcm9vbXMgYmVjYXVzZSBvZiBzdGFmZmluZyBjdXRzLiBWaXNpdG9ycyBtdXN0IGJlIGFibGUgdG8gZW50ZXIgdXNpbmcgYXQgbGVhc3Qgb25lIG9mIHRoZSB0d28gcm9vbXMgYXQgb25lIGVuZCBvZiB0aGUgZ2FsbGVyeSwgcHJvY2VlZCB0aHJvdWdoIHRoZSBnYWxsZXJ5LCBhbmQgZXhpdCBmcm9tIGF0IGxlYXN0IG9uZSBvZiB0aGUgdHdvIHJvb21zIGF0IHRoZSBvdGhlciBlbmQuIFRoZXJlZm9yZSwgdGhlIGN1cmF0b3IgbXVzdCBub3QgY2xvc2Ugb2ZmIGFueSB0d28gcm9vbXMgdGhhdCB3b3VsZCBibG9jayBwYXNzYWdlIHRocm91Z2ggdGhlIGdhbGxlcnkuIFRoYXQgaXMsIHRoZSBjdXJhdG9yIG1heSBub3QgYmxvY2sgb2ZmIHR3byByb29tcyBpbiB0aGUgc2FtZSByb3cgb3IgdHdvIHJvb21zIGluIGFkamFjZW50IHJvd3MgdGhhdCB0b3VjaCBkaWFnb25hbGx5LiBGdXJ0aGVybW9yZSwgc2hlIGhhcyBkZXRlcm1pbmVkIGhvdyBtdWNoIHZhbHVlIGVhY2ggcm9vbSBoYXMgdG8gdGhlIGdlbmVyYWwgcHVibGljLCBhbmQgbm93IHNoZSB3YW50cyB0byBjbG9zZSBvZmYgdGhvc2UgayByb29tcyB0aGF0IGxlYXZlIHRoZSBtb3N0IHZhbHVlIGF2YWlsYWJsZSB0byB0aGUgcHVibGljLCB3aXRob3V0IGJsb2NraW5nIHBhc3NhZ2UgdGhyb3VnaCB0aGUgZ2FsbGVyeS48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlclwiPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlczJcL2dhbGxlcnkucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MzUxcHg7IHdpZHRoOjkwcHhcIiBcLz48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlclwiPkZpZ3VyZSBILjE6IFRoZSBhcnQgZ2FsbGVyeSBzaG93cyBhbiBvcHRpbWFsIHNvbHV0aW9uIHRvIHRoZSB0aGlyZCBzYW1wbGUgaW5wdXQgcHJvYmxlbS4gVGhlIGdyYXkgcm9vbXM8YnIgXC8+XHJcbnNob3cgdGhvc2UgdGhhdCBzaG91bGQgYmUgY2xvc2VkLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+SW5wdXQgd2lsbCBjb25zaXN0IG9mIG11bHRpcGxlIHByb2JsZW0gaW5zdGFuY2VzIChnYWxsZXJpZXMpLiBFYWNoIHByb2JsZW0gaW5zdGFuY2Ugd2lsbCBiZWdpbiB3aXRoIGEgbGluZSBjb250YWluaW5nIHR3byBpbnRlZ2VycyBOIGFuZCBrLCB3aGVyZSAzICZsZTsgTiAmbGU7IDIwMCBnaXZlcyB0aGUgbnVtYmVyIG9mIHJvd3MsIGFuZCAwICZsZTsgayAmbGU7IE4gZ2l2ZXMgdGhlIG51bWJlciBvZiByb29tcyB0aGF0IG11c3QgYmUgY2xvc2VkIG9mZi4gVGhpcyBpcyBmb2xsb3dlZCBieSBOIHJvd3Mgb2YgdHdvIGludGVnZXJzLCBnaXZpbmcgdGhlIHZhbHVlcyBvZiB0aGUgdHdvIHJvb21zIGluIHRoYXQgcm93LiBFYWNoIHJvb20mcnNxdW87cyB2YWx1ZSB2IHNhdGlzZmllcyAwICZsZTsgdiAmbGU7IDEwMC4gQSBsaW5lIGNvbnRhaW5pbmcgMCAwIHdpbGwgZm9sbG93IHRoZSBsYXN0IGdhbGxlcnk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBnYWxsZXJ5LCBvdXRwdXQgdGhlIGFtb3VudCBvZiB2YWx1ZSB0aGF0IHRoZSBnZW5lcmFsIHB1YmxpYyBtYXkgb3B0aW1hbGx5IHJlY2VpdmUsIG9uZSBsaW5lIHBlciBnYWxsZXJ5LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==