Problem C
Universeum

Universeum in Gothenburg is planning to renovate and install $N$ infinitely large aquariums.

There are $M$ types of fish, each type $i$ having a unique mass $m_i$ and a number $a_i$ of fish.

Two fish can only live together in the same aquarium if the difference in their mass is strictly less than $D$. Otherwise, they will eat each other, which is, of course, something we don’t want to happen!

How many fish can Universeum maximally fit into their aquariums?

Input

The first line contains three integers, $N$, $M$, $D$ $(1 \leq N, M \leq 2 \cdot 10^5), (1 \leq D \leq 10^9)$. $N$ is the number of aquariums, $M$ is the number of different fish types, and $D$ is the maximum allowable difference in the mass of two fish in the same aquarium.

The following $M$ lines describe each fish type. Each line contains two integers, $a_i$, $m_i$, $(1 \leq a_i \leq 10^6)$, $(1 \leq m_i \leq 10^9)$, which means there are $a_i$ fish of type $i$, each with mass $m_i$.

Output

Print an integer, the maximum number of fish that Universeum can fit into their aquariums.

Scoring

Your solution will be tested on several different test groups. To earn points for a group, you must pass all test cases in the group.

Explanation

In the first example case, you can first place the $1000$ fish with mass $11$ in one aquarium. Then, you can place the $10$ fish with mass $1$ together with the $100$ fish with mass $3$ in another aquarium. This way, a total of $1110$ fish can be accommodated.

In the second example case, we have five aquariums and five types of fish. Therefore, each fish type can get its own aquarium, and we can fit all $15$ fish.

2 5 3
1000 11
100 8
100 3
10 1
1 5

1110

5 5 1
1 1000000000
2 9
3 5
4 9
5 11

15

1 10 6
1 1
1 2
10 3
1 4
1 5
10 6
1 7
1 8
10 9
1 10

24