Paul jest właścicielem firmy cateringowej, a interesy idą znakomicie. Firma ma $k$ zespołów cateringowych, z których każdy odpowiada za jeden zestaw sprzętu. Co tydzień firma przyjmuje $n$ zleceń obsługi różnych imprez. Dla każdego zlecenia wysyła zespół ze sprzętem na miejsce imprezy. Zespół dostarcza jedzenie, ustawia sprzęt i instruuje gospodarza, jak go używać i podawać jedzenie. Po imprezie gospodarz odpowiada za zwrot sprzętu do firmy Paula.

Zdjęcie z Wikimedia Commons

Niestety, w niektórych tygodniach zespołów jest mniej niż zleceń, więc niektóre zespoły muszą obsłużyć więcej niż jedną imprezę. W takich przypadkach firma nie może czekać na zwrot sprzętu przez gospodarza i musi pozostawić zespół na miejscu, aby przewiózł sprzęt w inne miejsce. Firma dysponuje dokładnym oszacowaniem kosztu przewozu zestawu sprzętu z dowolnego miejsca do dowolnego innego. Znając te koszty, Paul chce przygotować Advance Catering Map, aby zrealizować zlecenia, minimalizując łączny koszt przewozu sprzętu (w tym pierwszego przewozu), nawet jeśli oznacza to niewykorzystanie wszystkich dostępnych zespołów. Paul potrzebuje twojej pomocy w napisaniu programu wykonującego to zadanie. Zlecenia są uporządkowane rosnąco według terminów imprez i dobrane tak, że dla dowolnych $i<j$ jest wystarczająco dużo czasu, aby przewieźć sprzęt użyty w $i$-tym zleceniu do miejsca $j$-tego zlecenia.

Wejście

Pierwszy wiersz wejścia zawiera dwie liczby całkowite $n$ ($1 \le n \le 100$) i $k$ ($1 \le k \le 100$), oznaczające odpowiednio liczbę zleceń i zespołów cateringowych. Następnie występuje $n$ wierszy, przy czym $i$-ty zawiera $n-i+1$ liczb całkowitych od $0$ do $1\,000\,000$ włącznie. $j$-ta liczba w $i$-tym wierszu jest kosztem przewozu zestawu sprzętu z miejsca $i$ do miejsca $i+j$. Firma znajduje się w miejscu $1$, a $n$ zleceń w miejscach od $2$ do $n+1$.

Wyjście

Wypisz minimalny koszt przewozu pozwalający obsłużyć wszystkie zlecenia. (Kwota ta nie obejmuje kosztu przewozu sprzętu z powrotem do firmy cateringowej.)

Przykład

Wejście 1

3 2
40 30 40
50 10
50

Wyjście 1

80

Wejście 2

3 2
10 10 10
20 21
21

Wyjście 2

40