프로그램 명: coci_domine
제한시간: 1 초
Nx3 크기의 격자판이 있어서 각 격자마다 정수가 써져있다. 당신은 이 격자판에 아래 방법과 같이 K개의 1x2크기의 도미노를 올리려고 한다.
-
각 도미노는 정확히 두 개의 격자판을 덮어야 한다.
-
한 격자에 두 개 이상의 도미노를 덮거나 도미노가 격자판 밖을 벗어나면 안 된다.
-
도미노는 돌릴 수 있다.
-
K개의 도미노를 모두 사용해야 한다.
-
도미노에 의해 덮힌 격자들에 써져있는 수들의 합은 최대가 되어야 한다.
격자판이 주어질 때, 당신이 얻을 수 있는 값을 구하는 프로그램을 출력하여라.
입력 형식
-
첫 번째 줄에는 격자판의 크기 N과 도미노의 개수 K가 주어진다.
(1 ≤ N, K ≤ 1,000)
-
두 번째 줄에는 격자판에 써져있는 수가 주어진다. 이 수는 -10^6 이상 10^6 이하의 정수이다.
출력 형식
도미노에 의해 덮힌 격자들에 써져있는 수들의 합의 최댓값을 출력한다.
Mirko has a chessboard with N rows and just three columns. Slavica has written an integer on each
field. Mirko has K dominoes at his disposal, their dimensions being 2x1, and has to arrange all of them
on the board without overlapping, in a way that each domino covers exactly two fields of the board. He
can rotate the dominoes as he pleases.
Help Mirko cover the largest sum of numbers possible with the dominoes!
입력
-
The first line of input contains the integer N (1 ≤ N ≤ 1000), the number of rows, and K (1 ≤ K ≤
1000), the number of dominoes available.
-
Each of the following N lines contains three integers written in the i-th row of the board. All numbers will be lesser than 10^6 by absolute value.
출력
The first and only line of output must contain the maximal sum possible to cover with exactly K dominoes.
입출력 예
input
5 3
2 1 -1
1 3 2
0 2 3
2 1 1
3 3 0
output
16
input
2 2
0 4 1
3 5 1
output
13
Clarification of the first example: It is optimal to place all dominoes horizontally and along the right edge of the second row, right edge of the third row and along the left edge of the final row.
출처:/coci/2013-2014/contest5
번역:funtionx
[질/답]
[제출 현황]
[푼 후(1)]