Tembelizor

tv

== include(page="template/taskheader" task_id="tv") ==

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 upgradua 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, dispozitibul 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 fii afisata cea mai apropiata culoare de $V$ (sau 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 minim. Observam ca deoarece tembelizorul este initial alb-negru, in cel mai rau caz fiecare culoare va fi reprezentata de $1$ (alb) sau $C$ (negru).
Scopul lui Bill este sa plateasca o suma minima de bani pentru a isi upgradua tembelizorulm 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.

Poveste şi cerinţă...

h2. Date de intrare