P8586 Starring Defense Facility

An asteroid swarm from outside the Milky Way is about to launch an organized strike on Earth.

According to observations, there will be a total of $n$ waves of asteroid swarms attacking the Solar System. Each wave has two attributes: $d_i, m_i$, meaning that the $i$-th wave will start on the $d_i$-th solar day, and the total mass of the swarm is $m_i$. Without precise defense, the Solar System may face a catastrophic disaster. Therefore, your boss assigns you the task of building the Starring Defense Facility. More specifically, the Starring Defense Facility can destroy at most a total asteroid mass of $k$ per solar day. For an asteroid swarm that appears on the $d$-th solar day, if the facility cannot destroy it on day $d$ or day $d+1$ (or can only destroy part of it), then the swarm (or its remaining part) will be handed over to the Earth Peace Joint Organization TPC to handle—you certainly do not want someone else to take over your job! So, you want to know: what is the maximum total asteroid mass that the Starring Defense Facility under your command can destroy?

The first line contains two integers $n, k$, meaning there are $n$ waves of asteroid swarms, and at most mass $k$ can be destroyed per solar day. Lines $2$ to $n+1$ each contain two non-negative integers $d_i, m_i$, with meanings as described above.

Output one line with an integer $ans$, representing the maximum total mass of asteroids that can be destroyed.

For $10\%$ of the testdata, $1\leq n,\max\{d_i\} \leq 20$. For $20\%$ of the testdata, $1\leq n,\max\{d_i\}\leq 600$. For $40\%$ of the testdata, $1\leq n,\max\{d_i\}\leq 5000$. For another $10\%$ of the testdata, the sum of all $m_i$ is guaranteed to be no more than $k$. For $100\%$ of the testdata, $1\leq n,\max\{d_i\}\leq 3\times 10^5$, $0\leq m_i,k\leq 10^4$. Translated by ChatGPT 5