metrouri

În Ţara lui Stuf-Vodă există o linie de metrou cu $N$ staţii, numerotate cu $1, 2, \dots, N$ plasate pe o dreaptă la distanţe egale, de la stânga la dreapta. MetroStuf dispune de K metrouri care circulă pe această linie. Acestea pleacă din staţia $1$ către staţia $N$. Timpul de deplasare a unui metrou între două staţii consecutive este de un minut.

Stuf-Vodă vrea însă să îşi ţină oameni cât mai fericiţi, aşa că vrea să găsească un scenariu optim de plecare a metrourilor din staţia $1$ către staţia $N$, astfel încât oameni să aştepte cât mai puţin. Se dau $M$ perechi de forma $(S_i, T_i)$ cu semnificaţia: în staţia $S_i$ la minutul $T_i$ ajunge o persoană. Se defineşte costul unui metrou, ca fiind timpul cel mai mare de aşteptare al unei persoane, care s-a urcat în metroul respectiv. Stuf-Vodă şi-a dat seama că oamenii din ţara lui sunt cu atât mai fericiţi cu cât suma costurilor metrourilor este mai mică. O persoană urcă întotdeauna în primul metrou care soseşte în staţie.

Cerință

Dându-se $N$, $M$, $K$ şi $M$ perechi de forma $(S_i, T_i)$ cu semnificaţia de mai sus, se cere să se calculeze momentele de timp la care trebuie să plece metrourile din staţia 1 către staţia $N$, astfel încât suma costurilor metrourilor să fie minimă.

Date de intrare

Pe prima linie a fişierului metrouri.in se vor găsi trei numere: $N$, $M$ şi $K$ separate prin câte un spaţiu, cu semnificaţia din enunţ. Pe următoarele $M$ linii se vor găsi câte două numere, $S_i$ şi $T_i$, cu semnificaţia că la momentul de timp $T_i$ în staţia Si ajunge o persoană.

Date de ieșire

Fisierului de ieşire metrouri.out va conţine un singur număr şi anume suma costurilor celor $K$ metrouri.

Restricții și precizări

• $1 \leq N, M, K \leq 100 \ 000$
• Metrourile nu merg decât într-un singur sens şi odată ajunse în staţia $N$ rămân acolo până la sfârşitul zilei
• Pentru $30\%$ din teste $N \leq 200, M \leq 1000, K \leq 100$
• Pentru $60\%$ din teste $N \leq 10 \ 000, M \leq 20 \ 000, K \leq 300$
• $1 \leq S_i \leq N$
• $0 \leq T_i \leq 1 \ 000 \ 000$
• MetroStuf se deschide la minutul $0$ (persoanele nu pot ajunge mai devreme de aceasta ora în staţii), însă metrourile pot pleca din staţia $1$ înainte de acest moment.
• În oricare metrou pot să urce oricâte persoane.

Exemplu

metrouri.in

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

metrouri.out

3

Explicație

Metroul $1$ pleacă din staţia $1$ la minutul $2$, metroul $2$ pleacă la minutul $6$, iar metroul $3$ la minutul $8$. Costul metroului $1$ este $1$, costului metroului $2$ este $1$, iar costul metroului $3$ este $0$. Suma costurilor metrourilor este $2$.