# Domine

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 $2 \times 1$, 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 please

Help Mirko cover *the largest sum of numbers
possible* with the dominoes!

## Input

The first line of input contains the integer $N$ ($1 \le N \le 1000$), the number of rows, and $K$ ($1 \le K \le 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 less than $10^6$ in absolute value.

## Output

The first and only line of output must contain the maximal sum possible to cover with exactly $K$ dominoes.

Sample Input 1 | Sample Output 1 |
---|---|

5 3 2 1 -1 1 3 2 0 2 3 2 1 1 3 3 0 |
16 |

Sample Input 2 | Sample Output 2 |
---|---|

2 2 0 4 1 3 5 1 |
13 |