시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 128 MB 298 75 55 26.442%

문제

상근이는 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
W3sicHJvYmxlbV9pZCI6Ijk5MzYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNjYjRcdWMyYTRcdWI4NWMgXHViM2M0XHViYmY4XHViMTc4XHViOTdjIFx1ZDBjMFx1Yzc5MCIsImRlc2NyaXB0aW9uIjoiPHA+XHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IE5cdWQ1ODkgM1x1YzVmNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHVjY2I0XHVjMmE0XHVkMzEwXHVjNzQ0IFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWIyZTQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YWMwMCBcdWM3YTBcdWMyZGMgXHVjNjc4XHVjZDljXHVkNTVjIFx1YzBhY1x1Yzc3NCBcdWNjM2RcdWM2MDFcdWM3NzRcdWIyOTQgXHVjY2I0XHVjMmE0XHVkMzEwXHVjNzU4IFx1YmFhOFx1YjRlMCBcdWNlNzhcdWM1ZDAgXHVjODE1XHVjMjE4XHViOTdjIFx1YzM3Y1x1YWNlMCwgXHViYzE0XHViMmU1XHVjNWQwIFx1YjNjNFx1YmJmOFx1YjE3OCBLXHVhYzFjXHViOTdjIFx1YjE5M1x1YWNlMCBcdWIzYzRcdWI5ZGRcdWFjMTRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzY3OFx1Y2Q5Y1x1YzVkMFx1YzExYyBcdWIzY2NcdWM1NDRcdWM2MjggXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YzU2MFx1YzljMFx1YzkxMVx1YzljMCBcdWQ1NThcdWIyOTQgXHVjY2I0XHVjMmE0XHVkMzEwXHVjNWQwIFx1YzIyYlx1Yzc5MFx1YWMwMCBcdWMzNjhcdWM3ODhcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1YmNmNFx1YWNlMCBcdWQwNzAgXHVjZGE5XHVhY2E5XHVjNWQwIFx1YmU2MFx1Yzg0Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjYzNkXHVjNjAxXHVjNzc0XHViMjk0IFx1YzBjMVx1YWRmY1x1Yzc3NFx1YWMwMCBcdWMyYWNcdWQzN2NcdWQ1NThcdWIyOTQgXHViYWE4XHVjMmI1XHVjNzQ0IFx1YWNhY1x1YjUxYyBcdWMyMThcdWFjMDAgXHVjNWM2XHVjNWM4XHViMmU0LiBcdWNjM2RcdWM2MDFcdWM3NzRcdWIyOTQgXHViM2M0XHViYmY4XHViMTc4XHViOTdjIFx1YmFhOFx1YjQ1MCBcdWMwYWNcdWM2YTlcdWQ1NzQgXHVjY2I0XHVjMmE0XHVkMzEwXHVjNzQ0IFx1YjM2ZVx1YzczY1x1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YjNjNFx1YmJmOFx1YjE3OFx1Yzc1OCBcdWQwNmNcdWFlMzBcdWIyOTQgMiZ0aW1lczsxXHVjNzc0XHVhY2UwLCBcdWIzYzRcdWJiZjhcdWIxNzhcdWI5N2MgXHViYWE4XHViNDUwIFx1YzBhY1x1YzZhOVx1ZDU3NCBcdWNjYjRcdWMyYTRcdWQzMTBcdWM3NDQgXHViMzZlXHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHViM2M0XHViYmY4XHViMTc4XHViMjk0IFx1YzExY1x1Yjg1YyBcdWFjYjlcdWNlNjAgXHVjMjE4IFx1YzVjNlx1YWNlMCwgXHVkNjhjXHVjODA0IFx1YzJkY1x1ZDBhYyBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWIzYzRcdWJiZjhcdWIxNzhcdWIyOTQgXHVkNTZkXHVjMGMxIFx1Y2NiNFx1YzJhNFx1ZDMxMFx1Yzc1OCBcdWI0NTAgXHVjZTc4XHVjNzQ0IFx1Y2MyOFx1YzljMFx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjNjNFx1YmJmOFx1YjE3OFx1Yjk3YyBcdWM3NzRcdWM2YTlcdWQ1NzQgXHVjY2I0XHVjMmE0XHVkMzEwXHVjNzQ0IFx1YjM2ZVx1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NDAgXHVjNWVjXHViN2VjIFx1YWMwMFx1YzljMFx1YWMwMCBcdWM3ODhcdWIyZTQuIFx1Yzc3NCBcdWI1NGMsIFx1YjNjNFx1YmJmOFx1YjE3OFx1Yjg1YyBcdWIzNmVcdWM3NDAgXHVjZTc4XHVjNWQwIFx1YzM2OCBcdWM3ODhcdWIyOTQgXHVjMjE4XHVjNzU4IFx1ZDU2OVx1Yzc1OCBcdWNkNWNcdWIzMDBcdWFjMTJcdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIE5cdWFjZmMgS1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgTiAmbGU7IDEwMDAsIDEgJmxlOyBLICZsZTsgMTAwMCk8XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIE5cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1Y2NiNFx1YzJhNFx1ZDMxMFx1Yzc1OCBpXHViYzg4XHVjOWY4IFx1ZDU4OVx1YzVkMCBcdWMzNjggXHVjNzg4XHViMjk0IFx1YzIyYlx1Yzc5MCBcdWMxMzggXHVhYzFjXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViYWE4XHViNGUwIFx1YzIyYlx1Yzc5MFx1YjI5NCBcdWM4MDhcdWIzMDBcdWFjMTJcdWM3NzQgMTA8c3VwPjY8XC9zdXA+XHViY2Y0XHViMmU0IFx1Yzc5MVx1Yzc0MCBcdWM4MTVcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWIzYzRcdWJiZjhcdWIxNzggS1x1YWMxY1x1Yjk3YyBcdWM3NzRcdWM2YTlcdWQ1NzQgXHViMzZlXHVjNzQwIFx1Y2U3OFx1YzVkMCBcdWMzNjggXHVjNzg4XHViMjk0IFx1YzIxOFx1Yjk3YyBcdWJhYThcdWI0NTAgXHViMzU0XHVkNTg4XHVjNzQ0IFx1YjU0YywgXHVkNTY5XHVjNzU4IFx1Y2Q1Y1x1YjMwMFx1YWMxMlx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI5OTM2IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRE9NSU5FIiwiZGVzY3JpcHRpb24iOiI8cD5NaXJrbyBoYXMgYSBjaGVzc2JvYXJkIHdpdGggTiByb3dzIGFuZCBqdXN0IHRocmVlIGNvbHVtbnMuIFNsYXZpY2EgaGFzIHdyaXR0ZW4gYW4gaW50ZWdlciBvbiBlYWNoIGZpZWxkLiBNaXJrbyBoYXMgSyBkb21pbm9lcyBhdCBoaXMgZGlzcG9zYWwsIHRoZWlyIGRpbWVuc2lvbnMgYmVpbmcgMngxLCBhbmQgaGFzIHRvIGFycmFuZ2UgYWxsIG9mIHRoZW0gb24gdGhlIGJvYXJkIHdpdGhvdXQgb3ZlcmxhcHBpbmcsIGluIGEgd2F5IHRoYXQgZWFjaCBkb21pbm8gY292ZXJzIGV4YWN0bHkgdHdvIGZpZWxkcyBvZiB0aGUgYm9hcmQuIEhlIGNhbiByb3RhdGUgdGhlIGRvbWlub2VzIGFzIGhlIHBsZWFzZXMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkhlbHAgTWlya28gY292ZXIgdGhlIGxhcmdlc3Qgc3VtIG9mIG51bWJlcnMgcG9zc2libGUgd2l0aCB0aGUgZG9taW5vZXMhJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyB0aGUgaW50ZWdlciBOICgxICZsZTsgTiAmbGU7IDEwMDApLCB0aGUgbnVtYmVyIG9mIHJvd3MsIGFuZCBLICgxICZsZTsgSyAmbGU7IDEwMDApLCB0aGUgbnVtYmVyIG9mIGRvbWlub2VzIGF2YWlsYWJsZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgZm9sbG93aW5nIE4gbGluZXMgY29udGFpbnMgdGhyZWUgaW50ZWdlcnMgd3JpdHRlbiBpbiB0aGUgaTxzdXA+dGg8XC9zdXA+IHJvdyBvZiB0aGUgYm9hcmQuIEFsbCBudW1iZXJzIHdpbGwgYmUgbGVzc2VyIHRoYW4gMTA2IGJ5IGFic29sdXRlIHZhbHVlLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBmaXJzdCBhbmQgb25seSBsaW5lIG9mIG91dHB1dCBtdXN0IGNvbnRhaW4gdGhlIG1heGltYWwgc3VtIHBvc3NpYmxlIHRvIGNvdmVyIHdpdGggZXhhY3RseSBLIGRvbWlub2VzLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiI8cD5JdCBpcyBvcHRpbWFsIHRvIHBsYWNlIGFsbCBkb21pbm9lcyBob3Jpem9udGFsbHkgYW5kIGFsb25nIHRoZSByaWdodCBlZGdlIG9mIHRoZSBzZWNvbmQgcm93LCByaWdodCBlZGdlIG9mIHRoZSB0aGlyZCByb3cgYW5kIGFsb25nIHRoZSBsZWZ0IGVkZ2Ugb2YgdGhlIGZpbmFsIHJvdy4mbmJzcDs8XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==