Mirko has a chessboard with rows and just three columns. Slavica has written an integer on each field. Mirko has dominoes at his disposal, their dimensions being , 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!

#### Input Specification

The first line of input contains the integer , the number of rows, and , the number of dominoes available.

Each of the following lines contains three integers written in the row of the board. All numbers will be less than by absolute value.

#### Output Specification

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

#### Sample Input 1

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

#### Sample Output 1

`16`

#### Explanation for Sample Output 1

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.

#### Sample Input 2

```
2 2
0 4 1
3 5 1
```

#### Sample Output 2

`13`

## Comments