Paul besitzt ein Cateringunternehmen, und das Geschäft floriert. Das Unternehmen hat $k$ Cateringteams, von denen jedes für einen Satz Cateringausrüstung verantwortlich ist. Jede Woche nimmt das Unternehmen $n$ Cateringaufträge für verschiedene Veranstaltungen an. Für jeden Auftrag schickt es ein Team mit seiner Ausrüstung zum Veranstaltungsort. Das Team liefert das Essen, baut die Ausrüstung auf und erklärt dem Gastgeber, wie er die Ausrüstung benutzt und das Essen serviert. Nach der Veranstaltung ist der Gastgeber dafür verantwortlich, die Ausrüstung zu Pauls Unternehmen zurückzubringen.

Bild von Wikimedia Commons

Leider gibt es in manchen Wochen weniger Teams als Aufträge, sodass einige Teams für mehr als eine Veranstaltung eingesetzt werden müssen. In diesen Fällen kann das Unternehmen nicht warten, bis der Gastgeber die Ausrüstung zurückbringt, sondern muss das Team vor Ort lassen, damit es die Ausrüstung zu einem anderen Ort transportiert. Das Unternehmen hat eine genaue Schätzung der Kosten, einen Satz Ausrüstung von jedem Ort zu jedem anderen zu transportieren. Anhand dieser Kosten möchte Paul eine Advance Catering Map erstellen, um die Aufträge bei minimalen gesamten Transportkosten der Ausrüstung (einschließlich des ersten Transports) zu erfüllen, selbst wenn dafür nicht alle verfügbaren Teams eingesetzt werden. Paul braucht deine Hilfe, um ein Programm für diese Aufgabe zu schreiben. Die Aufträge sind aufsteigend nach ihren Veranstaltungszeiten sortiert und so gewählt, dass für beliebige $i<j$ genügend Zeit bleibt, die beim $i$-ten Auftrag verwendete Ausrüstung zum Ort des $j$-ten Auftrags zu transportieren.

Eingabe

Die erste Eingabezeile enthält zwei ganze Zahlen $n$ ($1 \le n \le 100$) und $k$ ($1 \le k \le 100$), die Anzahl der Aufträge beziehungsweise der Cateringteams. Darauf folgen $n$ Zeilen, wobei die $i$-te Zeile $n-i+1$ ganze Zahlen zwischen $0$ und $1\,000\,000$ einschließlich enthält. Die $j$-te Zahl in der $i$-ten Zeile sind die Kosten für den Transport eines Satzes Ausrüstung von Ort $i$ zu Ort $i+j$. Das Unternehmen befindet sich an Ort $1$, die $n$ Aufträge an den Orten $2$ bis $n+1$.

Ausgabe

Gib die minimalen Transportkosten zur Erfüllung aller Aufträge aus. (Dieser Betrag enthält nicht die Kosten für den Rücktransport der Ausrüstung zum Cateringunternehmen.)

Beispiele

Eingabe 1

3 2
40 30 40
50 10
50

Ausgabe 1

80

Eingabe 2

3 2
10 10 10
20 21
21

Ausgabe 2

40