Problem C
Universeum

Universeum i Göteborg planerar att renovera och installera $N$ oändligt stora akvarium.

Det finns $M$ fisksorter där varje sort $i$ har en unik massa $m_i$ och ett antal $a_i$ fiskar.

Två fiskar får endast bo tillsammans i ett akvarium om skillnaden i deras massa är strikt mindre än $D$, annars äter de upp varandra vilket vi såklart inte vill ska hända!

Hur många fiskar kan Universeum maximalt få plats med i sina akvarium?

Indata

Första raden innehåller tre heltal, $N$, $M$, $D$ $(1 \leq N,M \leq 2\cdot 10^5), (1 \leq D \leq 10^9)$. $N$ är antalet akvarium, $M$ antal olika fisksorter, och $D$ är den maximala skillnaden i massa av två fiskar i samma akvarium.

De följande $M$ raderna beskriver en fisksort på vardera rad. På varje rad finns två heltal, $a_i$, $m_i$, $(1 \leq a_i \leq 10^6)$, $(1 \leq m_i \leq 10^9)$, som innebär att det finns $a_i$ fiskar av fisksort $i$ som har massa $m_i$.

Utdata

Skriv ut ett heltal, det maximala antalet fiskar som universeum kan få plats med i sina akvarium.

Poängsättning

Din lösning kommer att testas på flera olika testgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

Förklaring

I det första exempelfallet kan man först ha de $1000$ fiskarna med massa $11$ i ett akvarium. Sedan kan man ha de $10$ fiskarna med massa $1$ tillsammans med de $100$ fiskarna med massa $3$ i ett akvarium. Då har vi sammanlagt fått plats med $1110$ fiskar.

I det andra exempelfallet har vi fem akvarium och fem fisksorter. Därför kan alla fisksorter få sitt egna akvarium och vi får plats med alla $15$ fiskarna.

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