Catering

Paul runs a catering company and the business is busy. The company has $k$ catering teams, and each team is in charge of one set of catering equipment. Every week the company accepts $n$ catering requests for different events. For each request the company sends one team with its equipment to the event location. The team delivers the food, sets up the equipment, and shows the host how to use the equipment and how to serve the food. After the event the host returns the equipment to the company.

In some weeks the number of teams is smaller than the number of requests, so one team has to work more than one event. In that case the company cannot wait for the host to return the equipment, so the team stays on site and moves the equipment straight to the next location. The company knows the exact cost of moving one set of equipment from any location to any other location. Paul wants a plan that serves all $n$ requests with the smallest total moving cost, counting the first move out of the company. Using fewer than $k$ teams is allowed.

The requests are sorted in ascending order of event time, and for any two requests with $i < j$ there is enough time to move the equipment used for the $i$th request to the location of the $j$th request.

The first line contains the number of requests $n$ ($1 \le n \le 100$) and the number of catering teams $k$ ($1 \le k \le 100$). Each of the next $n$ lines describes one location: line $i$ contains $n - i + 1$ integers between 0 and 1000000 inclusive, and the $j$th number on line $i$ is the cost of moving one set of equipment from location $i$ to location $i + j$. The company is at location 1, and the $n$ requests are at locations 2 to $n + 1$, one request per location.

Print the minimum total moving cost that serves all requests. This amount does not include the cost of moving equipment back to the catering company.

Two different teams must not go to the same location. The starting location is the only location that more than one team can be at.