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$ 行には $0$ 以上 $1\,000\,000$ 以下の整数が $n-i+1$ 個含まれます。第 $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