P7675 [COCI 2013/2014 #5] DOMINE

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.

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 one integer, representing the maximum sum of the numbers on the board that can be covered by these $K$ dominoes.

**[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](https://hsin.hr/coci/archive/2013_2014/) [CONTEST #5](https://hsin.hr/coci/archive/2013_2014/contest5_tasks.pdf) _**T4 DOMINE**_. Translated by ChatGPT 5