Informática Avançado – Semana 72

Sofhia e as gôndolas

Sofhia está no parque de diversões. E agora ela está em uma fila na frente da roda gigante. Existem $n$ pessoas (ou raposas, mais precisamente) na fila: usamos as primeiras pessoas para indicar uma no início da fila e a $n$-ésima pessoa para referir a última na fila.

Haverá $k$ gôndolas, e a maneira como alocamos as gôndolas é assim:

• Quando a primeira gôndola chegar, as $q_1$ pessoas na frente da fila entram na gôndola.
• Então, quando a segunda gôndola chegar, as $q_2$ pessoas na frente da fila restante vão para a gôndola.
• …
• As $q_k$ pessoas restantes vão para a última (k-ésima) gôndola.

Note que $q_1, q_2, q_3, ..., q_n$ são quantidades positivas. Você pode tirar do enunciado que $\sum_{i=1}^{n} q_i = n$.

Você sabe, as pessoas não querem ficar com estranhos nas gôndolas. Portanto, sua tarefa é encontrar uma maneira ideal de alocação (ou seja, encontrar uma sequência ideal q) para fazer as pessoas felizes. Para cada par de pessoas $i$ e $j$, existe um valor $u_{ij}$ que denota um nível de familiaridade. Você pode assumir $u_{ij} = u_{ji}$ para todos os $i, j$ $(1 \leq i, j \leq n)$ e $u_{ii} = 0$ para todos os $i$ $(1 \leq i \leq n)$. Então, um valor não familiar de uma gôndola é a soma dos níveis de não familiar entre qualquer par de pessoas que esteja nas gôndolas.

Entrada

A primeira linha contém dois números inteiros $n$ e $k$ $(1 \leq n \leq 4000$ $e$ $1 \leq k \leq min(n, 800))$ – o número de pessoas na fila e o número de gôndolas. Cada uma das $n$ linhas a seguir contém $n$ números inteiros – matriz $u$, $(0 \leq u_{ij} \leq 9, u_{ij} = u_{ji}$ $e$ $u_{ii} = 0)$.

Por favor, use métodos de entrada rápidos (por exemplo, use BufferedReader em vez do Scanner para Java).

Saída

Imprimir um número inteiro – o mínimo total de desfamiliriaridade possível.

Exemplos

Enviar solução: codeforces