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

ENTRADA SAÍDA
5 2

0 0 1 1 1

0 0 1 1 1

1 1 0 0 0

1 1 0 0 0

1 1 0 0 0

 0
ENTRADA SAÍDA
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

 7
ENTRADA SAÍDA
3 2

0 2 0

2 0 3

0 3 0

 2

Enviar solução: codeforces