14177번 - 티떱랜드

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

이 놀이기구에는 총 K개의 열차가 있으며, 다음과 같이 사람들을 태워야 한다.

• 첫 번째 열차에 줄의 앞에서부터 q₁명을 태워야 한다.
• 두 번째 열차에 첫 번째 열차를 타고 줄의 앞에서부터 q₂명을 태워야 한다.
• ...
• K번째 열차에 남은 q_K명을 태워야 한다.

q₁, q₂, ..., q_K는 항상 양수이며, Σq_i = n 이다.

티떱랜드의 사장 민혁이는 사람들이 모르는 사람과 놀이기구를 타는 일을 좋아하지 않는다는 것을 알고 있다. 오늘 민혁이는 사람들을 행복하게 만들기 위해서 최적의 q₁, q₂, ..., q_K값을 찾으려고 한다.

모든 i번 사람과 j번 사람 사이에는 어색한 정도 u_ij가 정의되어 있다. u_ij = u_ji이며, 모든 1 ≤ i ≤ N에 대해서, u_ii = 0이다.

열차의 어색함은 놀이기구에 타 있는 모든 사람들의 쌍의 어색한 정도의 합이다.

열차의 어색함의 합을 최소로 하는 q₁, q₂, ..., q_K를 찾는 프로그램을 작성하시오.

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

둘째 줄부터 N개의 줄에는 N개의 정수가 주어지며, 이것은 행렬 u (0 ≤ u_ij ≤ 9, u_ij = u_ji, u_ii = 0)을 나타낸다.

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

첫 번째 예제의 경우에는 (1, 2), (3, 4, 5)로 타고, 두 번째 예제의 경우에는 (1, 2, 3), (4, 5, 6), (7, 8)로 타면 최소다.