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