== include(page="template/taskheader" task_id="tv") ==
Poveste şi cerinţă...
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.
h2. Date de intrare
Fişierul de intrare $tv.in$ ...
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$.
h2. Date de ieşire
În fişierul de ieşire $tv.out$ ...
Fişierul de ieşire $tv.out$ va contine un singur numar natural, costul minim pentru a face tembelizorul sa perceapa imaginea "clara".
h2. 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$
h2. Exemplu
table(example). |_. tv.in |_. tv.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|3 3 7
5 1 6
6 4 6
5 4 3
4 4 4 5 6
|13
|
h3. Explicaţie
...
== include(page="template/taskfooter" task_id="tv") ==
