Paul 開咗一間到會公司，生意好興旺。公司有 $k$ 支到會團隊，每隊負責一套到會設備。公司每個星期會接 $n$ 個唔同活動嘅到會要求。每接一個要求，公司都會派一隊人帶埋設備去活動地點。團隊會送食物、裝好設備，並教主辦人點樣用設備同埋供餐。活動完咗之後，主辦人負責將設備送返 Paul 嘅公司。

圖片來自 Wikimedia Commons

可惜，有啲星期到會團隊數目少過要求數目，所以有啲團隊可能要服務多過一個活動。喺呢種情況下，公司唔可以等主辦人交返設備，而要留隊人喺現場，將設備搬去另一個地點。公司準確知道將一套設備由任何地點搬去另一個地點嘅費用。畀定呢啲費用，Paul 想制定一份 Advance Catering Map，滿足所有要求，同時令設備搬運總費用（包括第一次搬運嘅費用）盡量低，就算唔用晒所有可用團隊都冇問題。Paul 需要你幫手寫程式完成呢項工作。要求已經按活動時間遞增排序，而且揀選方式保證：對任何 $i<j$，都有足夠時間將第 $i$ 個要求所用嘅設備搬去第 $j$ 個要求嘅地點。

輸入格式

輸入第一行有兩個整數 $n$（$1 \le n \le 100$）同埋 $k$（$1 \le k \le 100$），分別代表要求數目同到會團隊數目。之後有 $n$ 行，第 $i$ 行有 $n-i+1$ 個由 $0$ 到 $1\,000\,000$（包括兩端）嘅整數。第 $i$ 行第 $j$ 個數係將一套設備由地點 $i$ 搬去地點 $i+j$ 嘅費用。公司喺地點 $1$，而 $n$ 個要求喺地點 $2$ 到 $n+1$。

輸出格式

輸出滿足所有要求所需嘅最小搬運費用。（呢個金額唔包括將設備搬返到會公司嘅費用。）

樣例

輸入格式 1

3 2
40 30 40
50 10
50

輸出格式 1

80

輸入格式 2

3 2
10 10 10
20 21
21

輸出格式 2

40