Score : $500$ points
Takahashi has an integer $x$. Initially, $x = 0$.
There are $N$ operations. The $i$-th operation $(1 \leq i \leq N)$ is represented by two integers $t_i$ and $y_i$ as follows:
Takahashi may skip any number between $0$ and $K$ (inclusive) of the operations. When he performs the remaining operations once each without changing the order, find the maximum possible final value of $x$.
Input is given from Standard Input in the following format:
$N$ $K$ $t_1$ $y_1$ $\vdots$ $t_N$ $y_N$
Print the answer.
5 1 2 4 2 -3 1 2 2 1 2 -3
3
If he skips the $5$-th operation, $x$ changes as $0 \rightarrow 4 \rightarrow 1 \rightarrow 2 \rightarrow 3$, so $x$ results in $3$. This is the maximum.
1 0 2 -1000000000
-1000000000
10 3 2 3 2 -1 1 4 2 -1 2 5 2 -9 2 2 1 -6 2 5 2 -3
15