Có n học sinh tham giac một câu lạc bộ của trường đứng thành một hàng ngang, đánh số \(1, 2, ..., n\) từ trái qua phải. Thầy giáo muốn chia \(n\) bạn thành \(m\) nhóm, mỗi nhóm là một dãy các bạn học sinh liên tiếp và tối thiểu phải có 1 bạn.
Vì các bạn học sinh đến từ nhiều lớp khác nhau nên không phải \(a_i\) cũng quen biết \(a_i\). Mức độ không quen biết của bạn học sinh \(i\) và bạn học sinh \(j\) được đặc trưng bởi số nguyên \(a_{i,j}\). Mức độ không quen biết của một nhóm là nửa tổng mức độ không quen biết của các cặp học sinh bất kỳ trong nhóm (tính cả \(a_{i,j}\) và \(a_{j,i}\) và \(a_{i,i}\)).

Yêu cầu: Hãy chia \(n\) bạn học sinh thành \(m\) nhóm sao cho tổng mức độ không quen biết của các nhóm là nhỏ nhất.

Input

• 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