Fişierul intrare/ieşire:	magazin.in, magazin.out	Sursă	preONI 2007, Runda 3
Autor	Mircea Bogdan Pasoi	Adăugată de	Mircea Pasoi •domino
Timp execuţie pe test	0.025 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	5/5

Vezi solutiile trimise | Statistici

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:

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 pe care se afla), si iese prin coltul dreapta-jos al magazinului. Determinati un astfel de traseu de distanta minima pentru Zaharel.

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.

Date de iesire

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

Restrictii

• 1 ≤ P ≤ 300
• 1 ≤ N ≤ 350
• 1 ≤ M ≤ 25
• 1 ≤ D ≤ 5
• 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

Exemplu

Explicatie

...

Cum se trimit solutii?