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