티떱랜드

티떱랜드에서 가장 인기 있는 놀이기구 앞에 $N$명이 한 줄로 서 있다. 1번 사람이 줄의 가장 앞에 있고, $N$번 사람이 가장 뒤에 있다.

이 놀이기구에는 열차가 $K$대 있고, 사람들은 다음 순서로 탄다.

• 첫 번째 열차에 줄의 앞에서부터 $q_1$명이 탄다.
• 두 번째 열차에 그 다음 $q_2$명이 탄다.
• 같은 방식으로 계속해서, $K$번째 열차에 남은 $q_K$명이 탄다.

$q_1, q_2, \dots, q_K$는 모두 양수이고 $\sum q_i = N$이다.

티떱랜드 사장 민혁이는 사람들이 모르는 사람과 함께 놀이기구를 타기 싫어한다는 사실을 알고 있다. 민혁이는 오늘 사람들을 행복하게 만들려고 최적의 $q_1, q_2, \dots, q_K$를 찾는다.

$i$번 사람과 $j$번 사람 사이에는 어색한 정도 $u_{ij}$가 정해져 있다. $u_{ij} = u_{ji}$이고, 모든 $1 \le i \le N$에 대해 $u_{ii} = 0$이다.

한 열차의 어색함은 그 열차에 탄 사람으로 만들 수 있는 모든 쌍의 어색한 정도를 더한 값이다.

열차 $K$대의 어색함의 합을 최소로 하는 $q_1, q_2, \dots, q_K$를 찾는 프로그램을 작성하시오.

첫째 줄에 사람의 수 $N$과 열차의 수 $K$가 주어진다. ($1 \le N \le 4000$, $1 \le K \le \min(N, 800)$)

둘째 줄부터 $N$개의 줄에 각각 정수 $N$개가 주어진다. 이 수가 행렬 $u$를 나타낸다. ($0 \le u_{ij} \le 9$, $u_{ij} = u_{ji}$, $u_{ii} = 0$)

열차의 어색함의 합의 최솟값을 출력한다.

첫 번째 예제에서는 (1, 2)와 (3, 4, 5)로 나누어 타면 최솟값이 된다.

두 번째 예제에서는 (1, 2, 3), (4, 5, 6), (7, 8)로 나누어 타면 최솟값이 된다.