Choo Choo

A train runs from city 1 to city $N$. It passes the cities in increasing order of their numbers: city 1, city 2, city 3, and so on up to city $N$. At most $P$ people can be on the train at any moment.

$A_{i,j}$ people want to travel from city $i$ to city $j$, and the fare for that trip is $C_{i,j}$ per person. A passenger boards only at the city they start from and gets off only at the city they are going to. The train picks freely which of the waiting people to take, and a person is either taken in full or not taken at all.

Write a program that computes the largest revenue the train can earn.

The first line contains the number of cities $N$ and the train capacity $P$. ($1 \le N \le 50$, $1 \le P \le 100$)

The next $N-1$ lines contain the numbers of people. The $j$-th number on the $i$-th line is $A_{i,i+j}$, the number of people who want to go from city $i$ to city $i+j$. The $i$-th line has $N-i$ numbers. ($0 \le A_{i,j} \le 100$)

The next $N-1$ lines contain the fares. The $j$-th number on the $i$-th line is $C_{i,i+j}$, the fare per person from city $i$ to city $i+j$. The $i$-th line has $N-i$ numbers. ($1 \le C_{i,j} \le 100$)

If $N$ is 1, both tables are empty and the input ends after the first line.

Print the largest revenue the train can earn.

In the first example the train earns the most with the following plan.

At city 1 it takes 2 people going from city 1 to city 2, 2 people going from city 1 to city 3, and 1 person going from city 1 to city 4. The revenue so far is $5 \times 2 + 3 \times 2 + 4 \times 1 = 20$.

At city 2 it drops the 2 people going to city 2 and takes 4 people going from city 2 to city 3. The revenue becomes $20 + 6 \times 4 = 44$.

At city 3 it drops the 2 people who came from city 1 and the 4 people who came from city 2, then takes 6 people going from city 3 to city 4. The revenue becomes $44 + 1 \times 6 = 50$.

At city 4 everyone left on board gets off. The final revenue is 50.