Problem F
Improving IT

Your best friend is part of the business team at the Global Center for Parallel Computing (GCPC). She is responsible for buying and selling the hardware that is powering the system that will be in use for the next $n$ months. Currently, she is planning the CPU replacement cycle for a single CPU. To ensure that the system is always up-to-date, the CPU must be replaced at least every $m$ months. Fortunately, she can sell the replaced CPU to lower the overall costs to operate the new system. However, storage capacity is pricey, and she has to accept the resale value the CPU has in the month it is replaced. That means, when a CPU that was used for $j$ months is replaced in month $i$, you need to sell the current CPU for the value it has after $j$ months of usage and buy a new CPU for the price of the $i$th month. She already compiled a list of CPU prices for the next $n$ months including their resale value after $1$ to $m$ months. Note that you definitely need to buy a CPU in month $1$ and you need to sell the last CPU in month $n + 1$. How much money does the system cost at least over the $n$ months?

Input

The input consists of:

• One line with two integers $n$ and $m$ ($1\leq n,m\text{ and } n \cdot m \leq 5 \cdot 10^5$).

• $n$ lines; the $i$th line has an integer $c$ ($0 \leq c \leq 10^9$), the cost of a CPU in month $i$, followed by $\min (m, n - i + 1)$ integers $c_j$ ($0 \leq c_j \leq 10^9$), the money you earn by selling this CPU after $j > 0$ months.

Output

Output a single integer, the minimum total cost. Note that this number can be negative if reselling CPUs was profitable.

Sample Input 1	Sample Output 1
4 3 1000 900 800 900 700 600 500 400 1200 1200 1300 600 500	100

Sample Input 2	Sample Output 2
3 2 200 300 400 400 300 200 300 500	-400