Paul possède une entreprise de service traiteur dont les affaires sont florissantes. L'entreprise dispose de $k$ équipes, chacune responsable d'un ensemble de matériel. Chaque semaine, elle accepte $n$ demandes de service traiteur pour divers événements. Pour chaque demande, une équipe est envoyée avec son matériel sur le lieu de l'événement. Elle livre les repas, installe le matériel et explique à l'organisateur comment l'utiliser et servir les repas. Après l'événement, l'organisateur est chargé de rapporter le matériel à l'entreprise de Paul.

Image provenant de Wikimedia Commons

Malheureusement, certaines semaines, le nombre d'équipes est inférieur au nombre de demandes, si bien que certaines équipes doivent intervenir sur plusieurs événements. Dans ce cas, l'entreprise ne peut pas attendre que l'organisateur rapporte le matériel et doit garder l'équipe sur place pour le transporter vers un autre lieu. L'entreprise dispose d'une estimation précise du coût de transport d'un ensemble de matériel entre n'importe quels lieux. Étant donné ces coûts, Paul souhaite préparer un Advance Catering Map pour satisfaire les demandes tout en minimisant le coût total de transport du matériel (y compris le premier déplacement), quitte à ne pas utiliser toutes les équipes disponibles. Paul a besoin de votre aide pour écrire un programme accomplissant cette tâche. Les demandes sont classées par ordre croissant des horaires des événements et sont choisies de telle sorte que, pour tous $i<j$, il y ait suffisamment de temps pour transporter le matériel utilisé pour la $i$-ème demande vers le lieu de la $j$-ème demande.

Entrée

La première ligne de l'entrée contient deux entiers $n$ ($1 \le n \le 100$) et $k$ ($1 \le k \le 100$), respectivement le nombre de demandes et le nombre d'équipes. Suivent $n$ lignes, dont la $i$-ème contient $n-i+1$ entiers compris entre $0$ et $1\,000\,000$, bornes incluses. Le $j$-ème nombre de la $i$-ème ligne est le coût de transport d'un ensemble de matériel du lieu $i$ au lieu $i+j$. L'entreprise est au lieu $1$ et les $n$ demandes se trouvent aux lieux $2$ à $n+1$.

Sortie

Affichez le coût minimal de transport pour satisfaire toutes les demandes. (Ce montant n'inclut pas le coût du retour du matériel à l'entreprise de service traiteur.)

Exemples

Entrée 1

3 2
40 30 40
50 10
50

Sortie 1

80

Entrée 2

3 2
10 10 10
20 21
21

Sortie 2

40