Cho một bảng ô vuông kích thước ~n \times 3~ (~n~ dòng và 3 cột), mỗi ô của bảng có điền một số nguyên. Steve có ~k~ quân domino kích thước ~2 \times 1~, mỗi quân domino có thể phủ đúng 2 ô kề cạnh của bảng. Steve đặ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 ý.

Yêu cầu: 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 \le n, k \le 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 là 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