Ride the dominoes on a chessboard

Time limit3sMemory limit128 MB

Summary

Place exactly K non-overlapping dominoes on an N by 3 board of integers to maximize the sum of covered cells.

Level: Medium7 of 10
Topics: Dynamic programming, Bit manipulation
Solved: No attempts yet

Problem

Sanggeun owns one chessboard with $N$ rows and 3 columns.

While Sanggeun was out for a moment, Changyoung wrote an integer in every square of the board, left $K$ dominoes lying on the floor, and ran away.

Sanggeun came home, saw the integers on the board he treasured, and was heartbroken.

Changyoung could not bear to watch Sanggeun grieve, so he decided to cover the board using all $K$ dominoes. One domino has size $2 \times 1$ and may be rotated. Dominoes cannot overlap, and one domino always covers two squares of the board. The board does not have to be covered without gaps, but every one of the $K$ dominoes has to be placed.

There are many ways to place the dominoes. Write a program that finds the largest sum you can get by adding up the numbers written in the squares the dominoes cover.

Input

The first line contains $N$ and $K$ . ( $1 \le N \le 1000$ , $1 \le K \le 1000$ )

Each of the next $N$ lines contains the three numbers written in one row of the board, given in order from the first row. Every number is an integer whose absolute value is smaller than $10^6$ .

The input satisfies $2K \le 3N$ , so the $K$ dominoes can always be placed.

Output

Print on the first line the largest sum of the numbers written in the squares covered by the $K$ dominoes.

Examples2

Example 1
Input
```
5 3
2 1 -1
1 3 2
0 2 3
2 1 1
3 3 0
```
Expected output
```
16
```
Example 2
Input
```
2 2
0 4 1
3 5 1
```
Expected output
```
13
```