Paul memiliki perusahaan katering dan bisnisnya sedang berkembang pesat. Perusahaan memiliki $k$ tim katering, masing-masing bertanggung jawab atas satu set peralatan. Setiap minggu, perusahaan menerima $n$ permintaan katering untuk berbagai acara. Untuk setiap permintaan, perusahaan mengirim tim beserta peralatannya ke lokasi acara. Tim mengantarkan makanan, memasang peralatan, serta mengajari tuan rumah cara menggunakan peralatan dan menyajikan makanan. Setelah acara, tuan rumah bertanggung jawab mengembalikan peralatan ke perusahaan Paul.

Gambar dari Wikimedia Commons

Sayangnya, pada beberapa minggu jumlah tim lebih sedikit daripada jumlah permintaan, sehingga beberapa tim mungkin harus menangani lebih dari satu acara. Dalam keadaan ini, perusahaan tidak dapat menunggu tuan rumah mengembalikan peralatan dan harus mempertahankan tim di lokasi untuk memindahkan peralatan ke lokasi lain. Perusahaan memiliki perkiraan akurat tentang biaya memindahkan satu set peralatan dari lokasi mana pun ke lokasi lain mana pun. Diberikan biaya-biaya ini, Paul ingin menyusun Advance Catering Map untuk memenuhi permintaan sambil meminimalkan total biaya pemindahan peralatan (termasuk pemindahan pertama), meskipun itu berarti tidak menggunakan semua tim yang tersedia. Paul membutuhkan bantuan Anda untuk menulis program yang menyelesaikan tugas ini. Permintaan diurutkan menaik berdasarkan waktu acara dan dipilih sedemikian rupa sehingga untuk setiap $i<j$, tersedia cukup waktu untuk mengangkut peralatan yang digunakan pada permintaan ke-$i$ ke lokasi permintaan ke-$j$.

Masukan

Baris pertama masukan berisi dua bilangan bulat $n$ ($1 \le n \le 100$) dan $k$ ($1 \le k \le 100$), masing-masing jumlah permintaan dan jumlah tim katering. Berikutnya terdapat $n$ baris, dengan baris ke-$i$ berisi $n-i+1$ bilangan bulat antara $0$ dan $1\,000\,000$, termasuk kedua batasnya. Bilangan ke-$j$ pada baris ke-$i$ adalah biaya memindahkan satu set peralatan dari lokasi $i$ ke lokasi $i+j$. Perusahaan berada di lokasi $1$ dan $n$ permintaan berada di lokasi $2$ hingga $n+1$.

Keluaran

Tampilkan biaya pemindahan minimum untuk memenuhi semua permintaan. (Jumlah ini tidak termasuk biaya mengembalikan peralatan ke perusahaan katering.)

Contoh

Masukan 1

3 2
40 30 40
50 10
50

Keluaran 1

80

Masukan 2

3 2
10 10 10
20 21
21

Keluaran 2

40