Caro

Vô tình bắt được Bờm đang loay hoay với bàn cờ Caro trong giờ học, thầy giáo đã phạt Bờm bằng việc giải một bài toán sau:

Cho một bảng hình chữ nhật gồm $4$ hàng và $n$ cột. Ô giao giữa hàng $i$ và cột $j$ được gọi là ô $(i,j)$. Trên mỗi ô có ghi một giá trị nguyên $A_{ij}$.

Công việc của Bờm là phải gạch tối đa $K$ đường thẳng, mỗi đường thẳng gồm các ô liên tiếp nhau trên cùng một hàng (một đường thẳng có thể chỉ gồm một ô). Hai đường thẳng khác nhau không được có ô chung. Bờm cần gạch sao cho tổng giá trị của các ô nằm trên các đường thẳng được gạch là lớn nhất. Bờm được phép không gạch đường nào, khi đó tổng bằng $0$.

Yêu cầu: Hãy giúp Bờm giải quyết bài toán trên.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên dương $n,K$ ($n\le 100$, $K\le 2·n$).
• $4$ dòng tiếp theo, dòng thứ $i$ chứa $n$ số nguyên $A_{i1},A_{i2},\dots ,A_{in}$ có giá trị tuyệt đối không vượt quá ${10}^9$.

Dữ liệu ra

In ra một số nguyên duy nhất là tổng giá trị lớn nhất tìm được.

Ràng buộc

• $1\le n\le 100$.
• $1\le K\le 2·n$.
• $|A_{ij}|\le {10}^9$.

Ví dụ