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 distanta minima a unui astfel de traseu.

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

h2. Restrictii

* $1 ≤ P ≤ 300$
* $1 ≤ N ≤ 350$

* $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

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