Improving IT

시간 제한2초메모리 제한1024 MB

요약

월별 CPU 가격과 사용 기간에 따른 중고 가치가 주어질 때, m개월마다 교체하며 n개월을 운영하는 최소 비용을 구한다.

난이도: 보통10점 중 6점
유형: 동적 계획법, 그리디, 슬라이딩 윈도우, 구현
정답자: 아직 제출이 없습니다

문제

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.

예제2

예제 1

입력

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

예상 출력

예제 2

입력

3 2
200 300 400
400 300 200
300 500

예상 출력

-400