Fișierul intrare/ieșire	paint1.in, paint1.out	Sursă	Lot I Juniori 2015
Autor	Constantin Gălățan	Adăugată de	Tiberiu Musat • Tiberiu02
Timp de execuție pe test	0.3 sec	Limită de memorie	8192 KB
Scorul tău	N/A	Dificultate	N/A

Vezi soluțiile trimise | Statistici

Paint1 (Lot Juniori)

Roberto are suflet de artist. El visează să ajungă într-o bună zi un pictor celebru, dar pentru moment își câștigă existența ca zugrav. Roberto a primit sarcina de a zugrăvi un zid având lungimea n metri și înălțimea un metru. Pentru aceasta are la dispoziție m zile. În fiecare zi i, el acoperă cu un singur strat de vopsea o porțiune compactă de înălțime un metru și de lungime l_i metri, începând de la distanța d_i metri față de capătul din stânga al zidului. Roberto știe din experiență că fiecare porțiune de zid trebuie acoperită cu cel puțin K straturi de vopsea pentru ca stratul final de vopsea să aibă consistența dorită. Din nefericire, firea lui de artist nu i-a permis să-și poată planifica munca în mod optim, astfel că la capătul celor m zile de efort, Roberto a constatat că zidul are porțiuni pe care le-a acoperit de mai mult de k ori și alte porțiuni pe care le-a acoperit de mai puțin de k ori.

Pentru a recupera în proprii săi ochi dar mai ales în ochii șefului de echipă, el trebuie să afle mai întâi suprafața totală a tuturor porțiunilor de zid care mai trebuie zugrăvite.

Cerință

Cunoscând lungimea zidului n, numărul de zile m și porțiunile compacte pe care le zugrăvește în fiecare zi, determinați suprafața totală a zidului care mai trebuie zugrăvită.

Date de intrare

Fișierul de intrare paint1.in conține pe prima linie trei numerele naturale n, k și m separate printr-un spațiu, unde n este lungimea zidului, k este numărul minim de straturi de vopsea pentru a se obține consistența dorită, iar m este numărul de zile în care Roberto pictează.

Pe următoarele m linii se află câte două valori naturale separate prin câte un spațiu. Numerele d_i și l_i de pe linia i+1 reprezintă distanța față de capătul din stânga al zidului de la care începe să zugrăvească în ziua i, respectiv lungimea în metri a porțiunii de zid zugrăvite în ziua i.

Date de ieșire

Fișierul de ieșire paint1.out conține pe prima linie un număr natural S care reprezintă suprafața totală a zidului care nu a fost acoperită cu cel puțin k straturi de vopsea.

Restricții

• 1 ≤ n, m ≤ 250 000
• 1 ≤ k ≤ min(250 000, m)
• 0 ≤ d_i < l_i < n

Exemplu

Explicație

n = 5, k = 2, m = 3.
În prima zi Roberto vopsește 2 m din zid între pozițiile 0 și 2. În a doua zi Roberto vopsește 3 m din zid între pozițiile 1 și 4. În a treia zi Roberto vopsește 3 m din zid între pozițiile 2 și 5. Deci, începând cu capătul din stânga al zidului, se va găsi o porțiune de zid de lungime 1, acoperită cu un singur strat și începând de la distanța 4 față de capăt, se va găsi o altă porțiune de zid de lungime 1, acoperită cu un singur strat