시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 128 MB 210 52 35 25.547%

문제

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

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

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

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

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

입력

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

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

출력

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

예제 입력

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

예제 출력

16

힌트