ARTICLES

Codeforces-190-Div1-E Ciel and Gondolas

By adam

June 5, 2020

E. Ciel and Gondolas

Fox Ciel went into an amusement park. She is in line for the Ferris wheel. There are $n$ foxes in the queue. We will assume that the first fox is at the beginning of the queue, and the $n$ th fox is at the tail of the queue.

In total there are $k$ gondolas. We distribute foxes into gondolas as follows:

When the first gondola swims up, $q_1$ foxes enter from the front of the line into the gondola. Then, when the second gondola swims up, $q_2$ foxes from the beginning of the remaining line go into this gondola.

…

The remaining $q_k$ foxes enter the last ($k$ th) gondola.

Note that the numbers $q_1 , q_2 , \cdots, q_k$ must be positive. From the condition it follows that and $q_i > 0$.

You know how foxes don’t want to linger in gondolas with strangers. So, your task is to find the optimal placement method (that is, determine the optimal sequence $q$) to please everyone. For each pair of foxes $i$ and $j$, a value $u_{ij}$ is given, which indicates the degree of unfamiliarity. You can assume that $u_{ij} = u_{ji}$ for all $i,j$ ($1 \le i,j \le n$) and that $u_{ii} = 0$ for all $i$ ($1 \le i \le n$). Then the value of unfamiliarity in the gondola is defined as the sum of the values of unfamiliarity between all pairs of foxes that are in this gondola. The total unfamiliarity value is defined as the sum of unfamiliarity values for all gondolas.

Help Fox Ciel find the minimum possible value for the total unfamiliarity with some optimal distribution of foxes in the gondolas.

Input data

The first line contains two integers $n$ and $k$ ($1 \le n \le 4000$ and $1 \le k \le \min ( n , 800)$ ) - the number of foxes in the queue and the number of gondolas. The next $n$ lines contain $n$ integers each - the matrix $u$, ( $0 ≤ $u_{ ij} \le 9$ , $u_{ij} = u_{ji}$ and $u_{ii} = 0$ ).

Please use quick read methods (for example, for Java use BufferedReader instead of Scanner).

Output

Print an integer - the minimum possible value of total unfamiliarity.

Examples

input data

output

input dataCopy 8 3 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 outputCopy 7 input dataCopy 3 2 0 2 0 2 0 3 0 3 0 outputCopy 2 Note In the first example, you can distribute the fox like this: {1, 2} go to one gondola, {3, 4, 5} go to another gondola.

In the second example, the optimal distribution is: {1, 2, 3} | {4, 5, 6} | {7, 8}.