Có n học sinh tham gia 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 ai cũng quen biết ai. 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ᵢⱼ (aⱼᵢ = aᵢⱼ, aᵢᵢ = 0). Mức độ không quen biết của một nhóm là tổng mức độ không quen biết của các cặp hai bạn học sinh bất kỳ trong nhóm.

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 ≤ n ≤ 4000, 1 ≤ m ≤ 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ᵢⱼ (0 ≤ aᵢⱼ ≤ 9, aᵢⱼ = aⱼᵢ, aᵢᵢ = 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: