2106. Домино

У Мирко есть шахматная доска, содержащая N горизонталей и всего три вертикали. Славица написал целое число на каждом клетке. Также Мирко есть `K` костяшек домино, каждая из которых может закрыть ровно две клетки на доске. Он должен расположить их все на доске без перекрытия и при этом может выбирать направление (вертикали или горизонтали) и место размещения костяшек.

Помогите Мирко покрыть костяшками домино наибольшую сумму чисел из возможных!

Первая строка ввода содержит целое число `N` (`1\ ≤\ N\ ≤\ 1000`) – количество горизонталей и `K` (`1\ ≤\ K\ ≤\ 1000`) – количество костяшек.

Каждая из следующих `N` строк содержит три целых числа, написанные на соответствущей горизонтали доски. Все числа меньше `10^6` по абсолютной величине.

Первый строка вывода должна содержать максимальную возможную сумму для покрытия точно `K` костяшками домино.

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

Пояснение к первому примеру: Оптимально все костяшки горизонтально – у правого края во втором ряду, затем у правого правого края в третьем ряду и у левого края в последнем ряду.