Fişierul intrare/ieşire:	tv.in, tv.out	Sursă	Algoritmiada 2016 - Runda 2, Seniori
Autor	Adrian Budau, Eugenie Daniel Posdarascu	Adăugată de	Adrian Budau •freak93
Timp execuţie pe test	0.3 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Tembelizor

Bill are un tembelizor. Bill nu are nevoie sa se dea mare fata de prietenii lui. Asta pentru ca Bill este sarac si nu a avut bani sa cumpere unul mai bun. Fii ca Bill.

Fie C numarul de culori distincte din universul lui Bill. Consideram 1 ca fiind alb si C ca fiind negru. Un tembelizor este un televizor alb-negru (percepe initial doar culorile 1 si C). Pentru fiecare culoare i de la 2 la C - 1, se cunoaste costul cost_i necesar pentru a upgrada tembelizorul astfel incat acesta sa perceapa si culoarea i.
Bill tocmai a aflat ca o poza cu el o sa apara la stiri. O imagine poate fii interpretata ca o matrice de N * M, valoarea din casuta de pe linia i coloana j reprezentand culoarea pixelului aflat la aceea pozitie. In momentul in care o imagine apare la tembelizor, dispozitivul afiseaza fiecare pixel conform urmatoarelor reguli:

• Daca avem un pixel de culoare V si tembelizorul percepe aceasta culoare, culoarea afisata pe ecran in acea pozitie este tot V
• Daca avem un pixel de culoare V, dar tembelizorul nu percepe aceasta culoare, in locul culorii V va fi afisata cea mai apropiata culoare de V (altfel spus culoarea aflata la distanta minima) perceputa de tembelizor. Distanta intre doua culori X si Y este valoarea absoluta a diferentei dintre cele doua culori: |X - Y|. In cazul in care exista mai multe culori aflate la distanta minima, se va alege culoarea cu indice maxim. Observam ca deoarece tembelizorul este initial alb-negru, in cel mai rau caz fiecare culoare va fi reprezentata fie de 1 (alb) fie de C (negru).

Scopul lui Bill este sa plateasca o suma minima de bani pentru a isi upgrada tembelizorul, astfel incat imaginea lui la stiri sa fie "clara". O imagine se considera "clara" daca oricum ai selecta 2 pixeli adiacenti din imagine de culori diferite, acestia sa apara cu culori diferite si la tembelizor.

Date de intrare

Fişierul de intrare tv.in va contine pe prima linie 3 numere naturale N, M si C. Pe urmatoarele N linii se vor afla cate M valori reprezentand culoarea fiecarui pixel din matrice (imaginea cu Bill care o sa apara la stiri). Pe ultima linie se vor afla C - 2 valori reprezentand vectorul cost. A i-a valoare este cost_i+1, costul necesar pentru a upgrada tembelizorul cu culoarea i+1.

Date de ieşire

Fişierul de ieşire tv.out va contine un singur numar natural, costul minim pentru a face tembelizorul sa perceapa imaginea "clara".

Restricţii

• 1 ≤ N,M ≤ 500
• 3 ≤ C ≤ 150.000
• Fiecare pixel o sa fie un numar natural din intervalul [1,C]
• 1 ≤ cost_i ≤ 1.000.000.000
• Pentru teste in valoare de 20 de puncte N, M, C ≤ 50
• Pentru teste in valoare de 30 de puncte C ≤ 500
• Pentru teste in valoare de 40 de puncte C ≤ 2.500

Exemplu

Cum se trimit solutii?