Mirko có một bàn cờ có ~N~ hàng và chỉ có ba cột. Slavica đã viết một số nguyên trên mỗi trường. Mirko có ~K~ quân domino tùy ý sử dụng, kích thước của chúng là ~2 \times 1~ và phải sắp xếp tất cả chúng trên bảng mà không bị chồng lên nhau, sao cho mỗi quân domino bao phủ chính xác hai ô của bàn cờ. Anh ta có thể xoay các quân domino theo ý muốn.

Giúp Mirko bao gồm tổng số lớn nhất có thể bằng quân domino!

Input

• Dòng đầu tiên chứa số nguyên ~N~ ~(1 \le N \le 1000)~, số hàng và ~K~ ~(1 \le K \le 1000)~, số lượng quân domino có sẵn.
• ~N~ dòng tiếp theo, mỗi dòng chứa ba số nguyên viết ở hàng thứ ~i~ của bảng. Tất cả các số sẽ nhỏ hơn ~10^6~ theo giá trị tuyệt đối.

Output

• Dòng đầu ra đầu tiên và duy nhất phải chứa tổng tối đa có thể bao phủ chính xác ~K~ domino.

Sample Input 1

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

Sample Output 1

16

Sample Input 2

2 2
0 4 1
3 5 1

Sample Output 2

13

Làm rõ ví dụ thứ nhất: Tốt nhất là đặt tất cả các quân domino theo chiều ngang và dọc theo mép phải của hàng thứ hai, mép phải của hàng thứ ba và dọc theo mép trái của hàng cuối cùng.