410588: GYM104059 I 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?

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 a single integer, the minimum total cost. Note that this number can be negative if reselling CPUs was profitable.

4 3
1000 900 800 900
700 600 500 400
1200 1200 1300
600 500

100

3 2
200 300 400
400 300 200
300 500

-400