== include(page="template/taskheader" task_id="paint1") ==
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.
h2. 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ă.
Poveste și cerință...
h2. 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$].
Fișierul de intrare $paint1.in$ ...
h2. 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.
În fișierul de ieșire $paint1.out$ ...
h2. Restricții
* $1 ≤ n, m ≤ 250 000$
* $1 ≤ k ≤ min(250 000, m)$
* $0 ≤ d[~i~] < l[~i~] < n$
* $... ≤ ... ≤ ...$
h2. Exemplu
table(example).
|_. paint1.in |_. paint1.out |
| 5 2 3
0 2
1 3
2 3
| 2
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. 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
...
== include(page="template/taskfooter" task_id="paint1") ==
== include(page="template/taskfooter" task_id="paint1") ==
