Nosaukums
Tastatūra (tasta)
Laika limits
1.00s
Atmiņas limits
64.0 MB
Grūtība
32%

Definīcija

Mazajam gudriniekam Pēterim jāuzraksta sacerējums. Viņš jau sacerēja visu tekstu, atlika tikai to uzrakstīt datorā. Tiesa, teksts ir pagarš, tāpēc Pēteris grib patērēt pēc iespējas mazāk laika, pārrakstot sacerējumu.

Pētera tastatūra ir × M taustiņus liela. Vienkāršības labad visi iespējamie simboli ir doti ar skaitļiem no 1 līdz · M. Katru no šiem simboliem var uzdrukāt ar tieši vienu taustiņu. Tastatūras rindiņas ir sanumurētas no 1 līdz N no augšas uz leju, un kolonnas no 1 līdz M no kreisās puses uz labo. Tāpēc katra taustiņa vietu var aprakstīt ar koordinātēm (i, j), kur i ir rindiņas numurs, bet j ir kolonnas numurs.

Pēteris drukā ar tikai diviem rādītājpirkstiem (šausmas!). Sākumā tie atrodas rūtiņās ar koordinātēm (N, 1) un (N, M). Pēteris drukā visus simbolus secīgi, un nekustina divas rokas vienlaicīgi (viņam tiešām jāiemācās drukāt normāli!). Vienā sekundē viņš var pabīdīt vienu no pirkstiem uz kādu no taustiņiem ar kopīgu malu. Lai uzspiestu taustiņu, netiek patērēts laiks. Abi pirksti vienlaicīgi var atrasties vienā rūtiņā. Kāds ir mazākais iespējamais laiks sekundēs, lai Pēteris varētu uzrakstīt sacerējumu uz datora?


Ievaddatu raksturojums

Pirmā rinda satur divus veselus skaitļus N un M, tastatūras izmērus (2 ≤ NM ≤ 10). Nākamās N rindas katra satur M skaitļus, kārtējās tastatūras rindas aprakstu. Garantēts, ka tastatūra satur katru no skaitļiem no 1 līdz · tieši vienu reizi.

Nākamā rinda satur skaitli K, teksta garumu (1 ≤ K ≤ 105). Pēdējā rinda satur K skaitļus a1, ..., aK, sacerējuma tekstu (1 ≤ ai ≤ · M).


Izvaddatu raksturojums

Izvadiet vienu skaitli, mazāko laiku sekundēs, kas vajadzīgs Pēterim, lai pilnībā pārrakstītu doto tekstu datorā!


Piezīmes

Apakšuzdevuma apraksts Punktu skaits
K ≤ 20 20
K ≤ 2000 50 
Bez papildus ierobežojumiem 30
Kopā:    100

Paraugdati

Stdin
3 4
2 10 4 7
6 1 8 11
5 12 9 3
6
5 4 12 2 1 7
Stdout
10

Uzdevums tiek aizsargāts ar autortiesībām un tā kopēšana vai neatļauta izmantošana ir aizliegta.