Description

You are given an $N \times 3$ board with numbers written on it. You have $K$ $1 \times 2$ dominoes. Please find the maximum possible sum of the numbers on the board that can be covered using these $K$ dominoes.

Input Format

The first line contains two integers $N$ and $K$, representing the number of rows of the board and the number of dominoes.

The next $N$ lines each contain $3$ integers, representing the numbers on the board.

Output Format

Output one integer, representing the maximum sum of the numbers on the board that can be covered by these $K$ dominoes.

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

16 

2 2
0 4 1
3 5 1 

13

Hint

[Sample Explanation #1]

As shown in the figure, the sum is $3+2+2+3+3+3=16$. It can be proven that this is the maximum.

[Constraints]

For $100\%$ of the testdata, $1 \le N, K \le 1000$.

[Notes]

The scoring of this problem follows the original COCI problem settings, with a full score of $120$.

This problem is translated from COCI2013_2014 CONTEST #5 T4 DOMINE.

Translated by ChatGPT 5