Xếp chỗ ngồi

Trong buổi sinh hoạt đầu tiên của một câu lạc bộ, có \(n\) thành viên mới đứng thành một hàng ngang, được đánh số từ \(1\) đến \(n\). Thầy giáo chủ nhiệm muốn chia các bạn thành \(m\) nhóm để tiện cho việc sinh hoạt và làm quen. Mỗi nhóm phải bao gồm một dãy các học sinh đứng liên tiếp nhau trong hàng và mỗi nhóm phải có ít nhất một thành viên.

Tuy nhiên, thầy giáo hiểu rằng các bạn học sinh đến từ nhiều lớp khác nhau nên không phải ai cũng đã quen biết nhau. Thầy đã tiến hành một cuộc khảo sát để xác định "mức độ không quen biết" giữa từng cặp học sinh. Mức độ không quen biết giữa bạn thứ \(i\) và bạn thứ \(j\) được cho bởi một số nguyên \(a_{i,j}\).

Để các nhóm hoạt động hiệu quả, thầy giáo muốn sắp xếp các nhóm sao cho tổng mức độ không quen biết của tất cả các nhóm là nhỏ nhất. Mức độ không quen biết của một nhóm được định nghĩa là nửa tổng mức độ không quen biết của tất cả các cặp học sinh bất kỳ trong nhóm đó.

Với \(n\) học sinh đứng thành một hàng và \(m\) nhóm cần chia, cùng với ma trận mức độ không quen biết \(A = [a_{ij}]\), hãy tìm cách chia các học sinh thành \(m\) nhóm liên tiếp sao cho tổng mức độ không quen biết của tất cả các nhóm là nhỏ nhất.

Input

Dữ liệu vào được cung cấp từ đầu vào chuẩn theo định dạng sau:

• Dòng đầu tiên chứa hai số nguyên dương \(n, m\) (\(1 \le n \le 4000, 1 \le m \le \min(n, 800)\)).
• \(n\) dòng tiếp theo, dòng thứ \(i\) chứa \(n\) số nguyên, số thứ \(j\) trên dòng thứ \(i\) là \(a_{ij}\) (\(0 \le a_{ij} \le 9, a_{ij} = a_{ji}, a_{ii} = 0\)).

Output

Một số nguyên duy nhất - tổng mức độ không quen biết nhỏ nhất của \(m\) nhóm

Example

3 2
0 2 0
2 0 3
0 3 0

2

Scoring

• Subtask \(1\) (\(30\%\) số điểm) : \(n \leq 20\).
• Subtask \(2\) (\(30\%\) số điểm) : \(n \leq 400\).
• Subtask \(3\) (\(40\%\) số điểm) : không có ràng buộc nào thêm.