체스로 도미노를 타자

상근이에게는 $N$행 3열짜리 체스판이 하나 있다.

상근이가 잠깐 자리를 비운 사이에 창영이는 체스판의 모든 칸에 정수를 하나씩 써 놓고, 바닥에 도미노 $K$개를 늘어놓은 채 달아났다.

집에 돌아온 상근이는 아끼던 체스판에 정수가 적힌 것을 보고 크게 상심했다.

창영이는 상근이가 슬퍼하는 모습을 차마 볼 수 없어서, 도미노 $K$개를 모두 써서 체스판을 덮기로 했다. 도미노 한 개의 크기는 $2 \times 1$이고, 회전시킬 수 있다. 도미노끼리 겹칠 수는 없고, 도미노 하나는 항상 체스판의 두 칸을 덮어야 한다. 체스판을 빈칸 없이 덮을 필요는 없지만, 도미노 $K$개는 하나도 남기지 않고 놓아야 한다.

도미노를 놓는 방법은 여러 가지다. 도미노가 덮은 칸에 적힌 수를 모두 더했을 때 나올 수 있는 합의 최댓값을 구하는 프로그램을 작성하시오.

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

다음 $N$개 줄에는 체스판의 각 행에 적힌 수 세 개가 첫째 행부터 차례대로 주어진다. 모든 수는 절댓값이 $10^6$보다 작은 정수이다.

도미노 $K$개를 항상 놓을 수 있도록, 입력은 $2K \le 3N$을 만족한다.

첫째 줄에 도미노 $K$개가 덮은 칸에 적힌 수의 합의 최댓값을 출력한다.