Cho một bảng ô vuông kích thước ~n×3~ (~n~ dòng và ~3~ cột), mỗi ô của bảng có điền một số nguyên nào đó. Quân có ~k~ quân domino kích thước ~2×1~, mỗi quân domino có thể phủ đúng hai ô kề cạnh của bảng. Quân đặt các quân domino của mình lên bảng sao cho mọi quân domino đều nằm trong bảng, mỗi quân phủ đúng ~2~ ô và không đè lên nhau. Có thể xoay quân domino tùy ý. Bạn hãy xác định tổng lớn nhất có thể đạt được của các số trên những ô bị phủ.

Input

• Dòng đầu tiên chứa ~2~ số nguyên ~n~ và ~k~ (~1 ≤ n~, ~k ≤ 1000~),
• Dòng thứ ~i~ trong ~n~ dòng sau chứa ~3~ số nguyên xác định các số ghi trên dòng ~i~ của bảng, các số có giá trị tuyệt đối không vượt quá ~10^6~.

Output

Một số nguyên – tổng lớn nhất của các số bị phủ.

Sample Input 1

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

Sample Output 1

16

Giới hạn:

• 30% số điểm tương ứng 30% số điểm có
• 30% số test khác có
• 40% số test còn lại tương ứng 40% số điểm có