Paul sở hữu một công ty cung cấp dịch vụ ăn uống và công việc kinh doanh đang phát đạt. Công ty có $k$ đội phục vụ, mỗi đội phụ trách một bộ thiết bị. Mỗi tuần, công ty nhận $n$ yêu cầu phục vụ ăn uống cho các sự kiện khác nhau. Với mỗi yêu cầu, công ty cử một đội cùng thiết bị đến địa điểm sự kiện. Đội giao thức ăn, lắp đặt thiết bị và hướng dẫn chủ tiệc sử dụng thiết bị cũng như phục vụ thức ăn. Sau sự kiện, chủ tiệc chịu trách nhiệm trả thiết bị về công ty của Paul.

Ảnh từ Wikimedia Commons

Đáng tiếc, có những tuần số đội phục vụ ít hơn số yêu cầu nên một số đội có thể phải phục vụ nhiều sự kiện. Khi đó, công ty không thể đợi chủ tiệc trả thiết bị mà phải giữ đội ở lại để chuyển thiết bị đến địa điểm khác. Công ty có ước tính chính xác về chi phí chuyển một bộ thiết bị từ bất kỳ địa điểm nào đến bất kỳ địa điểm nào khác. Với các chi phí này, Paul muốn lập một Advance Catering Map để đáp ứng các yêu cầu đồng thời tối thiểu hóa tổng chi phí vận chuyển thiết bị (kể cả lần chuyển đầu tiên), ngay cả khi điều đó có nghĩa là không dùng tất cả các đội hiện có. Paul cần bạn giúp viết chương trình thực hiện nhiệm vụ này. Các yêu cầu được sắp theo thời gian sự kiện tăng dần và được chọn sao cho với mọi $i<j$, luôn có đủ thời gian chuyển thiết bị dùng cho yêu cầu thứ $i$ đến địa điểm của yêu cầu thứ $j$.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên $n$ ($1 \le n \le 100$) và $k$ ($1 \le k \le 100$), lần lượt là số yêu cầu và số đội phục vụ. Tiếp theo là $n$ dòng, trong đó dòng thứ $i$ chứa $n-i+1$ số nguyên từ $0$ đến $1\,000\,000$, kể cả hai đầu mút. Số thứ $j$ trên dòng thứ $i$ là chi phí chuyển một bộ thiết bị từ địa điểm $i$ đến địa điểm $i+j$. Công ty ở địa điểm $1$, còn $n$ yêu cầu ở các địa điểm từ $2$ đến $n+1$.

Dữ liệu ra

In ra chi phí vận chuyển nhỏ nhất để đáp ứng tất cả các yêu cầu. (Số tiền này không bao gồm chi phí chuyển thiết bị trở về công ty.)

Ví dụ

Dữ liệu vào 1

3 2
40 30 40
50 10
50

Dữ liệu ra 1

80

Dữ liệu vào 2

3 2
10 10 10
20 21
21

Dữ liệu ra 2

40