Într-o bibliotecă se află 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 la . Fiecare dulap conţine de rafturi, situate vertical unul deasupra altuia, rafturile fiecărui dulap fiind numerotate de la la 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 până la un anumit nivel , ea va putea aduna orice carte de pe rafturile până la inclusiv, din dulapul şi din dulapurile învecinate (dulapul şi dulapul ).
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ă.
Cerință
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.
Date de intrare
Prima linie a fişierului de intrare rafturi.in conţine două numere naturale şi , 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 linii conţin câte două numere naturale și , separate printr-un spaţiu, reprezentând numărul dulapului, respectiv numărul raftului de unde trebuie luată o carte.
Date de ieșire
Fişierul de ieşire rafturi.out va conţine un singur număr natural reprezentând suma minimă a înălţimilor până la care trebuie să urce bibliotecara pentru a aduna toate cărţile cerute.
Restricții și precizări
Exemplu
rafturi.in
10 4
5 4
1 1
6 2
3 8
rafturi.out
11
Explicație
Bibliotecara urcă astfel:
- pe dulapul la raftul
- pe dulapul la raftul
- pe dulapul la raftul