COCI 2013/2014 - Contest 5- 도미노 (DOMINE) > 문제은행 : 정보올림피아드&알고리즘




2684 : 도미노 (DOMINE)

제한시간
1000 ms   
메모리제한
64 MB   
해결횟수
3 회   
시도횟수
14 회   

문제

Nx3 크기의 격자판이 있어서 각 격자마다 정수가 써져있다. 당신은 이 격자판에 아래 방법과 같이 K개의 1x2크기의 도미노를 올리려고 한다.

 

- 각 도미노는 정확히 두 개의 격자판을 덮어야 한다.

- 한 격자에 두 개 이상의 도미노를 덮거나 도미노가 격자판 밖을 벗어나면 안 된다.

- 도미노는 돌릴 수 있다.

- K개의 도미노를 모두 사용해야 한다.

- 도미노에 의해 덮힌 격자들에 써져있는 수들의 합은 최대가 되어야 한다.

 

격자판이 주어질 때, 당신이 얻을 수 있는 값을 구하는 프로그램을 출력하여라.


입력형식

첫 번째 줄에는 격자판의 크기 N과 도미노의 개수 K가 주어진다.(1 ≤ N, K ≤ 1,000) 두 번째 줄에는 격자판에 써져있는 수가 주어진다. 이 수는 -106 이상 106 이하의 정수이다.


출력형식

도미노에 의해 덮힌 격자들에 써져있는 수들의 합의 최댓값을 출력한다.


입력 예

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

출력 예

16

입력 예

2 2
0 4 1
3 5 1

출력 예

13

Hint!

입력예1 세 도미노가 2행 2열 - 2행 3열, 3행 2열 - 3행 3열, 5행 1열 - 5행 2열을 덮으면 최적이 된다.



경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP