Giải bài trực tuyến

Năm 2030, các tuyến đường sắt ở Việt Nam đã được nâng cấp. Trong đó hiện đại nhất là tuyến đường Bắc – Nam. Từ Hà Nội đi vào Sài Gòn chỉ mất 6 giờ đồng hồ(thay vì 30 giờ như trước). Tuyến đường này gồm N nhà ga, được đánh số từ 1 đến N. Tàu Bắc-Nam sẽ lần lượt đi qua các ga 1,2,…,N còn tàu Nam-Bắc đi theo lộ trình ngược lại. Trên tuyến đường Bắc-Nam có N-1 trạm dừng chân, trạm thứ i nằm giữa 2 nhà ga i và i+1. Các tàu đi qua một trạm sẽ đậu lại ở đó 30’ cho hành khách ăn uống, mua sắm, đi toilet, …

Để nâng cao chất lượng phục vụ cũng như thu hút thêm khách hàng, Tổng công ty Đường sắt Việt Nam (RVN) quyết định mở một đợt khuyến mãi. Ban giám đốc RVN chọn ra trong số N-1 trạm dừng chân K trạm “đặc biệt”. Mỗi hành khách lên tàu ở ga xuất phát sẽ được phát một phiếu ăn miễn phí. Tại mỗi trạm đặc biệt, mỗi người có phiếu sẽ được quyền gọi một suất ăn miễn phí. Sau khi gọi xong phiếu ăn sẽ được thu lại. Phiếu ăn của một hành khách sẽ mất giá trị khi người đó xuống tàu tại ga đến. Vậy nên không ai dại dột mà bỏ đi phần ăn của mình :D.

Do chi phí vận hành một trạm ăn miễn phí như vậy là gần như nhau tại tất cả các điểm, RVN muốn chọn K trạm đặc biệt sao cho tổng số khách hàng được phục vụ là nhiều nhất.

Input

         Dòng đầu tiên gồm 2 số nguyên N, K.
         N dòng tiếp theo, dòng thứ i gồm N số nguyên A[i,j] là số hành khách mua vé lên tàu ở ga xuất phát i và xuống tàu ở ga đến j.

         Giới hạn :  2 <= N <= 500

                        0 <= K <= N-1

                        0 <= a[i,j] <= 10⁵

                        a[i,i]=0

Output

         In ra một số nguyên là tổng số khách hàng nhiều nhất được phục vụ.

Example

Input:
4 2
0 5 0 6
2 0 5 3
3 1 0 5
0 4 7 0

Output:
35
Giải thích : RVN chọn 2 trạm 1 và 3