Magazin

magazin

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

Nargy si Fumeanu si-au deschis magazin. Acesta este aranjat astfel: sunt $N-1$ randuri de rafturi, intre rafturi existand $N$ culoare. Fiecare rand este format din $M$ rafturi de aceeasi marime. Distanta de la un raft la altul adiacent este de $1$ metru, iar distanta intre un culoar si alt culoar adiacent este de $D$ metri. De asemenea, distanta pentru a intra sau a iesi de pe culoar este de $1$ metru. Mai jos este o diagrama a magazinului, punctele gri reprezentand locurile in care te poti opri pe culoar pentru a cumpara produse de pe un raft:

Nargy si Fumeanu si-au deschis magazin. Acesta este aranjat astfel: sunt $N$ randuri de rafturi, intre rafturi existand culoare. Fiecare rand este format din $M$ rafturi de aceeasi marime. Distanta intre un culoar si alt culoar adiacent este de $D$ metri. U

p=. !problema/magazin?magazin.jpg!

Zaharel vine intr-o zi la magazin cu o lista de $P$ produse pe care vrea sa le cumpere. El intra in coltul stanga-jos al magazinului, cumpara cele $P$ produse de pe lista (pentru fiecare produs stie exact culoarul si raftul unde trebuie sa se afle), si iese prin coltul dreapta-jos al magazinului. Determinati distanta minima a unui astfel de traseu.
 

h2. Date de intrare

Fisierul de intrare $magazin.in$ va contine prima linie numerele naturale $P, N, M, D$ separate prin spatii. Urmatoarele $P$ linii vor contine cate doua numere naturale $x y$ cu semnificatia ca exista un produs pe care Zaharel vrea sa-l cumpere pe culoarul $x$, la raftul $y$.

...

h2. Date de iesire

Fisierul de iesire $magazin.out$ va contine un singur numar natural reprezentand distanta minima pe care Zaharel trebuie s-o parcurga.

...

h2. Restrictii

* $1 ≤ P ≤ 50.000$
* $1 ≤ N ≤ 30.000$
* $1 ≤ M ≤ 25$
* $1 ≤ D ≤ 5$
* Pentru $50%$ din teste $P ≤ 300, N ≤ 350$
* Pot exista mai multe produse pe acelasi culoar si acelasi raft
* Culoarele sunt numerotate cu numere de la $1$ la $N$ iar rafturile de pe un culoar cu numere de la $1$ la $M$, ca in diagrama

* $... ≤ ... ≤ ...$

h2. Exemplu
table(example). |_. magazin.in |_. magazin.out |

| 7 5 10 3
2 8
3 3
3 5
3 7
4 10
5 10
4 3
| 54

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|
h3. Explicatie

Ordinea in care Zaharel cumpara produsele este urmatoarea: $2, 3, 4, 1, 6, 5, 7$ (produsele au fost numerotate in functie de ordinea din fisierul de intrare).
 
!problema/magazin?magazin2.jpg!

...

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

1647