Magazin

magazin

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

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.

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 ≤ 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

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

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