== include(page="template/taskheader" task_id="metrouri") ==

În Ţara lui Stuf-Vodă există o linie de metrou cu $N$ staţii, numerotate cu $1, 2, …, 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.

În Ţara lui Stuf-Vodă există o linie de metrou cu $N$ staţii, numerotate cu $1, 2, …, 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.

* $1 ≤ N, M, K ≤ 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 ≤ 200, M ≤ 1000, K ≤ 100$
* Pentru $60 %$ din teste $N ≤ 10 000, M ≤ 20 000, K ≤ 300$

* Pentru $30%$ din teste $N ≤ 200, M ≤ 1000, K ≤ 100$
* Pentru $60%$ din teste $N ≤ 10 000, M ≤ 20 000, K ≤ 300$

* $1 ≤ S{~i~} ≤ N$
* $0 ≤ T{~i~} ≤ 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.

5671