Background

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

Problem Description

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?

Input Format

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 Format

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

3 3 
1 6
4 7
2 2

14

10 100
6 14
2 92
3 91
4 74
7 75
2 90
7 25
1 92
3 41
2 14

580

Hint

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