Paul é dono de uma empresa de catering e o negócio está a prosperar. A empresa tem $k$ equipas de catering, cada uma responsável por um conjunto de equipamento. Todas as semanas, aceita $n$ pedidos de catering para vários eventos. Para cada pedido, envia uma equipa com o seu equipamento para o local do evento. A equipa entrega a comida, instala o equipamento e ensina o anfitrião a utilizá-lo e a servir a comida. Depois do evento, o anfitrião é responsável por devolver o equipamento à empresa de Paul.

Imagem de Wikimedia Commons

Infelizmente, em algumas semanas há menos equipas do que pedidos, pelo que algumas equipas podem ter de servir mais de um evento. Nesses casos, a empresa não pode esperar que o anfitrião devolva o equipamento e tem de manter a equipa no local para o transportar para outro sítio. A empresa possui uma estimativa exata do custo de transportar um conjunto de equipamento de qualquer local para qualquer outro. Dados estes custos, Paul quer preparar um Advance Catering Map para satisfazer os pedidos minimizando o custo total de transporte do equipamento (incluindo o primeiro transporte), mesmo que isso implique não utilizar todas as equipas disponíveis. Paul precisa da tua ajuda para escrever um programa que realize esta tarefa. Os pedidos estão ordenados por ordem crescente dos horários dos eventos e foram escolhidos de modo que, para quaisquer $i<j$, haja tempo suficiente para transportar o equipamento usado no $i$-ésimo pedido para o local do $j$-ésimo pedido.

Entrada

A primeira linha da entrada contém dois inteiros $n$ ($1 \le n \le 100$) e $k$ ($1 \le k \le 100$), que são, respetivamente, o número de pedidos e o número de equipas de catering. Seguem-se $n$ linhas, em que a $i$-ésima contém $n-i+1$ inteiros entre $0$ e $1\,000\,000$, inclusive. O $j$-ésimo número da $i$-ésima linha é o custo de transportar um conjunto de equipamento do local $i$ para o local $i+j$. A empresa está no local $1$ e os $n$ pedidos estão nos locais de $2$ a $n+1$.

Saída

Apresenta o custo mínimo de transporte para satisfazer todos os pedidos. (Este valor não inclui o custo de transportar o equipamento de volta à empresa de catering.)

Exemplos

Entrada 1

3 2
40 30 40
50 10
50

Saída 1

80

Entrada 2

3 2
10 10 10
20 21
21

Saída 2

40