시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 128 MB85023816927.302%

문제

상근이는 N행 3열로 이루어진 체스판을 가지고 있다. 

상근이가 잠시 외출한 사이 창영이는 체스판의 모든 칸에 정수를 썼고, 바닥에 도미노 K개를 놓고 도망갔다.

외출에서 돌아온 상근이는 애지중지 하는 체스판에 정수가 쓰여 있는 것을 보고 큰 충격에 빠졌다.

창영이는 상근이가 슬퍼하는 모습을 견딜 수가 없었다. 창영이는 도미노를 모두 사용해 체스판을 덮으려고 한다. 도미노의 크기는 2×1이고, 도미노를 모두 사용해 체스판을 덮어야 한다. 도미노는 서로 겹칠 수 없고, 회전 시킬 수 있다. 도미노는 항상 체스판의 두 칸을 차지해야 한다.

도미노를 이용해 체스판을 덮는 방법은 여러 가지가 있다. 이때, 도미노로 덮은 칸에 쓰여 있는 수의 합의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 1000, 1 ≤ K ≤ 1000)

다음 N개 줄에는 체스판의 i번째 행에 쓰여 있는 수 세 개가 주어진다. 모든 수는 절댓값이 106보다 작은 정수이다.

출력

첫째 줄에 도미노 K개를 이용해 덮은 칸에 쓰여 있는 수를 모두 더했을 때, 합의 최댓값을 구하는 프로그램을 작성하시오.

예제 입력 1

5 3
2 1 -1
1 3 2
0 2 3
2 1 1
3 3 0

예제 출력 1

16

예제 입력 2

2 2
0 4 1
3 5 1

예제 출력 2

13
W3sicHJvYmxlbV9pZCI6Ijk5MzYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNjYjRcdWMyYTRcdWI4NWMgXHViM2M0XHViYmY4XHViMTc4XHViOTdjIFx1ZDBjMFx1Yzc5MCIsImRlc2NyaXB0aW9uIjoiPHA+XHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IE5cdWQ1ODkgM1x1YzVmNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHVjY2I0XHVjMmE0XHVkMzEwXHVjNzQ0IFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWIyZTQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YWMwMCBcdWM3YTBcdWMyZGMgXHVjNjc4XHVjZDljXHVkNTVjIFx1YzBhY1x1Yzc3NCBcdWNjM2RcdWM2MDFcdWM3NzRcdWIyOTQgXHVjY2I0XHVjMmE0XHVkMzEwXHVjNzU4IFx1YmFhOFx1YjRlMCBcdWNlNzhcdWM1ZDAgXHVjODE1XHVjMjE4XHViOTdjIFx1YzM3Y1x1YWNlMCwgXHViYzE0XHViMmU1XHVjNWQwIFx1YjNjNFx1YmJmOFx1YjE3OCBLXHVhYzFjXHViOTdjIFx1YjE5M1x1YWNlMCBcdWIzYzRcdWI5ZGRcdWFjMTRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzY3OFx1Y2Q5Y1x1YzVkMFx1YzExYyBcdWIzY2NcdWM1NDRcdWM2MjggXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YzU2MFx1YzljMFx1YzkxMVx1YzljMCBcdWQ1NThcdWIyOTQgXHVjY2I0XHVjMmE0XHVkMzEwXHVjNWQwIFx1YzgxNVx1YzIxOFx1YWMwMCBcdWM0ZjBcdWM1ZWMgXHVjNzg4XHViMjk0IFx1YWM4M1x1Yzc0NCBcdWJjZjRcdWFjZTAgXHVkMDcwIFx1Y2RhOVx1YWNhOVx1YzVkMCBcdWJlNjBcdWM4NGNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Y2MzZFx1YzYwMVx1Yzc3NFx1YjI5NCBcdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHVjMmFjXHVkMzdjXHVkNTU4XHViMjk0IFx1YmFhOFx1YzJiNVx1Yzc0NCBcdWFjYWNcdWI1MWMgXHVjMjE4XHVhYzAwIFx1YzVjNlx1YzVjOFx1YjJlNC4gXHVjYzNkXHVjNjAxXHVjNzc0XHViMjk0IFx1YjNjNFx1YmJmOFx1YjE3OFx1Yjk3YyBcdWJhYThcdWI0NTAgXHVjMGFjXHVjNmE5XHVkNTc0IFx1Y2NiNFx1YzJhNFx1ZDMxMFx1Yzc0NCBcdWIzNmVcdWM3M2NcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWIzYzRcdWJiZjhcdWIxNzhcdWM3NTggXHVkMDZjXHVhZTMwXHViMjk0IDImdGltZXM7MVx1Yzc3NFx1YWNlMCwgXHViM2M0XHViYmY4XHViMTc4XHViOTdjIFx1YmFhOFx1YjQ1MCBcdWMwYWNcdWM2YTlcdWQ1NzQgXHVjY2I0XHVjMmE0XHVkMzEwXHVjNzQ0IFx1YjM2ZVx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YjNjNFx1YmJmOFx1YjE3OFx1YjI5NCBcdWMxMWNcdWI4NWMgXHVhY2I5XHVjZTYwIFx1YzIxOCBcdWM1YzZcdWFjZTAsIFx1ZDY4Y1x1YzgwNCBcdWMyZGNcdWQwYWMgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHViM2M0XHViYmY4XHViMTc4XHViMjk0IFx1ZDU2ZFx1YzBjMSBcdWNjYjRcdWMyYTRcdWQzMTBcdWM3NTggXHViNDUwIFx1Y2U3OFx1Yzc0NCBcdWNjMjhcdWM5YzBcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIzYzRcdWJiZjhcdWIxNzhcdWI5N2MgXHVjNzc0XHVjNmE5XHVkNTc0IFx1Y2NiNFx1YzJhNFx1ZDMxMFx1Yzc0NCBcdWIzNmVcdWIyOTQgXHViYzI5XHViYzk1XHVjNzQwIFx1YzVlY1x1YjdlYyBcdWFjMDBcdWM5YzBcdWFjMDAgXHVjNzg4XHViMmU0LiBcdWM3NzRcdWI1NGMsIFx1YjNjNFx1YmJmOFx1YjE3OFx1Yjg1YyBcdWIzNmVcdWM3NDAgXHVjZTc4XHVjNWQwIFx1YzRmMFx1YzVlYyBcdWM3ODhcdWIyOTQgXHVjMjE4XHVjNzU4IFx1ZDU2OVx1Yzc1OCBcdWNkNWNcdWIzMTNcdWFjMTJcdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIE5cdWFjZmMgS1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgTiAmbGU7IDEwMDAsIDEgJmxlOyBLICZsZTsgMTAwMCk8XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIE5cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1Y2NiNFx1YzJhNFx1ZDMxMFx1Yzc1OCBpXHViYzg4XHVjOWY4IFx1ZDU4OVx1YzVkMCBcdWM0ZjBcdWM1ZWMgXHVjNzg4XHViMjk0IFx1YzIxOCBcdWMxMzggXHVhYzFjXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViYWE4XHViNGUwIFx1YzIxOFx1YjI5NCBcdWM4MDhcdWIzMTNcdWFjMTJcdWM3NzQgMTA8c3VwPjY8XC9zdXA+XHViY2Y0XHViMmU0IFx1Yzc5MVx1Yzc0MCBcdWM4MTVcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWIzYzRcdWJiZjhcdWIxNzggS1x1YWMxY1x1Yjk3YyBcdWM3NzRcdWM2YTlcdWQ1NzQgXHViMzZlXHVjNzQwIFx1Y2U3OFx1YzVkMCBcdWM0ZjBcdWM1ZWMgXHVjNzg4XHViMjk0IFx1YzIxOFx1Yjk3YyBcdWJhYThcdWI0NTAgXHViMzU0XHVkNTg4XHVjNzQ0IFx1YjU0YywgXHVkNTY5XHVjNzU4IFx1Y2Q1Y1x1YjMxM1x1YWMxMlx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiI5OTM2IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRE9NSU5FIiwiZGVzY3JpcHRpb24iOiI8cD5NaXJrbyBoYXMgYSBjaGVzc2JvYXJkIHdpdGggTiByb3dzIGFuZCBqdXN0IHRocmVlIGNvbHVtbnMuIFNsYXZpY2EgaGFzIHdyaXR0ZW4gYW4gaW50ZWdlciBvbiBlYWNoIGZpZWxkLiBNaXJrbyBoYXMgSyBkb21pbm9lcyBhdCBoaXMgZGlzcG9zYWwsIHRoZWlyIGRpbWVuc2lvbnMgYmVpbmcgMngxLCBhbmQgaGFzIHRvIGFycmFuZ2UgYWxsIG9mIHRoZW0gb24gdGhlIGJvYXJkIHdpdGhvdXQgb3ZlcmxhcHBpbmcsIGluIGEgd2F5IHRoYXQgZWFjaCBkb21pbm8gY292ZXJzIGV4YWN0bHkgdHdvIGZpZWxkcyBvZiB0aGUgYm9hcmQuIEhlIGNhbiByb3RhdGUgdGhlIGRvbWlub2VzIGFzIGhlIHBsZWFzZXMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkhlbHAgTWlya28gY292ZXIgdGhlIGxhcmdlc3Qgc3VtIG9mIG51bWJlcnMgcG9zc2libGUgd2l0aCB0aGUgZG9taW5vZXMhJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyB0aGUgaW50ZWdlciBOICgxICZsZTsgTiAmbGU7IDEwMDApLCB0aGUgbnVtYmVyIG9mIHJvd3MsIGFuZCBLICgxICZsZTsgSyAmbGU7IDEwMDApLCB0aGUgbnVtYmVyIG9mIGRvbWlub2VzIGF2YWlsYWJsZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgZm9sbG93aW5nIE4gbGluZXMgY29udGFpbnMgdGhyZWUgaW50ZWdlcnMgd3JpdHRlbiBpbiB0aGUgaTxzdXA+dGg8XC9zdXA+IHJvdyBvZiB0aGUgYm9hcmQuIEFsbCBudW1iZXJzIHdpbGwgYmUgbGVzc2VyIHRoYW4gMTA2IGJ5IGFic29sdXRlIHZhbHVlLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBmaXJzdCBhbmQgb25seSBsaW5lIG9mIG91dHB1dCBtdXN0IGNvbnRhaW4gdGhlIG1heGltYWwgc3VtIHBvc3NpYmxlIHRvIGNvdmVyIHdpdGggZXhhY3RseSBLIGRvbWlub2VzLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiI8cD5DbGFyaWZpY2F0aW9uIG9mIHRoZSBmaXJzdCBleGFtcGxlOiBJdCBpcyBvcHRpbWFsIHRvIHBsYWNlIGFsbCBkb21pbm9lcyBob3Jpem9udGFsbHkgYW5kIGFsb25nIHRoZSByaWdodCBlZGdlIG9mIHRoZSBzZWNvbmQgcm93LCByaWdodCBlZGdlIG9mIHRoZSB0aGlyZCByb3cgYW5kIGFsb25nIHRoZSBsZWZ0IGVkZ2Ugb2YgdGhlIGZpbmFsIHJvdy48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

Contest > Croatian Open Competition in Informatics > COCI 2013/2014 > Contest #5 4번

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: jh05013