Diferențe pentru problema/rafturi între reviziile #6 si #2

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

Într-o bibliotecă se află *C* dulapuri identice așezate unul lângă altul pe peretele unei încăperi, dulapurile fiind numerotate de la stânga spre dreapta cu numerele naturale de la 1 la *C*. Fiecare dulap conține 1000 de rafturi, situate vertical unul deasupra altuia, rafturile fiecărui dulap fiind numerotate de la 1 la 1000 de jos în sus.
 
Fiecare dulap este prevăzut cu o scară cu care se poate ajunge la orice raft. Dacă bibliotecara urcă scara unui anumit dulap *D* până la un anumit nivel *k*, ea va putea aduna orice carte de pe rafturile 1 până la *k* inclusiv, din dulapul *D* și din dulapurile învecinate (dulapul [*D*]-1 și dulapul [*D*]+1).
 

Într-o bibliotecă se află C dulapuri identice așezate unul lângă altul pe peretele unei încăperi, dulapurile fiind numerotate de la stânga spre dreapta cu numerele naturale de la 1 la C. Fiecare dulap conține 1000 de rafturi, situate vertical unul deasupra altuia, rafturile fiecărui dulap fiind numerotate de la 1 la 1000 de jos în sus.
Fiecare dulap este prevăzut cu o scară cu care se poate ajunge la orice raft. Dacă bibliotecara urcă scara unui anumit dulap D până la un anumit nivel k, ea va putea aduna orice carte de pe rafturile 1 până la k inclusiv, din dulapul D și din dulapurile învecinate (dulapul D-1 și dulapul D+1).

Cunoscând dulapurile și rafturile de unde trebuie luate cărți, bibliotecara dorește să adune toate cărțile cerute, dar suma înălțimilor până la care trebuie să urce să fie minimă.

h2. Cerință

h2. Cerinta

Scrieți un program care să determine suma minimă a înălțimilor până la care trebuie să urce bibliotecara pentru a aduna toate cărțile cerute.
h2. Date de intrare

Prima linie a fișierului de intrare $rafturi.in$ conține două numere naturale *C* și *N*, separate printr-un spațiu, reprezentând numărul dulapurilor și respectiv numărul cărților pe care bibliotecara trebuie să le adune. Următoarele *N* linii conțin câte două numere naturale *a* *b*, separate printr-un spațiu, reprezentând numărul dulapului, respectiv numărul raftului de unde trebuie luată o carte.

Prima linie a fișierului de intrare $rafturi.in$ conține două numere naturale C și N, separate printr-un spațiu, reprezentând numărul dulapurilor și respectiv numărul cărților pe care bibliotecara trebuie să le adune.
Următoarele N linii conțin câte două numere naturale a b, separate printr-un spațiu, reprezentând numărul dulapului, respectiv numărul raftului de unde trebuie luată o carte.

h2. Date de ieșire

h2. Restricții

* 1 ≤ *C* ≤ 10 000
* 1 ≤ *N* ≤ 50 000

$1 ≤ C ≤10000$
$1 ≤ N ≤50000$

h2. Exemplu

table(example).
|_. rafturi.in |_. rafturi.out |_. Explicatie |
| 10 4
5 4
1 1
6 2
3 8
| 11
| Bibliotecara urcă astfel:
-pe dulapul 1 la raftul 1
-pe dulapul 4 la raftul 8
-pe dulapul 6 la raftul 2
|

table(example).
|_. rafturi.in |_. rafturi.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
 
h3. Explicație
 
...

== include(page="template/taskfooter" task_id="rafturi") ==