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

Vi se dă o matrice de $N * N$ pixeli. Datoria voastră este să coloraţi fiecare pixel în alb sau negru astfel încât plăcerea vizuala să fie cât mai mare. Pentru a face asta trebuie să

Vi se dă o matrice de $N * N$ pixeli. Datoria voastră este să coloraţi fiecare pixel în alb sau negru astfel încât plăcerea vizuală să fie cât mai mare. Pentru a face asta trebuie să ştiţi 3 reguli. În primul rând, pentru fiecare pixel ştiţi cantitatea de plăcere $A{~ij~}$ pe care o provoacă dacă este colorat în alb. În al doilea rând, pentru fiecare pixel ştiţi cantitatea de plăcere $B{~ij~}$ pe care o provoacă dacă este colorat în negru. În al treilea rând, ştiţi pentru fiecare pereche de pixeli adiacenţi (adică au o muchie în comun) care este costul plăcerii $C{~ijk~}$ care trebuie *plătit* dacă sunt coloraţi diferit.
Costul plăcerii este dat pentru fiecare pixel şi pentru fiecare 4 direcţii. Cu alte cuvinte, pentru un anumit pixel la coordonate $(i, j)$, $C{~ij0~}$ este costul care trebuie plătit dacă acel pixel şi pixelul de la coordonatele $(i - 1, j)$ sunt coloraţi diferit, $C{~ij1~}$ este costul care trebuie plătit dacă acel pixel şi pixelul de la coordonatele $(i, j + 1)$ sunt coloraţi diferit, $C{~ij2~}$ este costul care trebuie plătit dacă acel pixel şi pixelul de la coordonatele $(i + 1, j)$ sunt coloraţi diferit, şi $C{~ij3~}$ este costul care trebuie plătit dacă acel pixel şi pixelul de la coordonatele $(i, j - 1)$ sunt coloraţi diferit.
Dacă un pixel nu are un vecin valid (adică unul care să facă parte din matrice), costul tot va fi dat, dar va fi 0. De exemplu $C{~110~}$ va fi întotdeauna 0. $C{~ij0~}$ şi $C{~i-1j2~}$ vor fi întotdeauna la fel, şi aşa mai departe (costul pentru fiecare pereche este simetric).
Voi trebuie să maximizaţi plăcerea totală, adică: *suma $A{~ij~}$ pentru toţi pixelii coloraţi în alb + suma $B{~ij~}$ pentru toţi pixelii coloraţi în negru - suma costurilor pixelilor adiacenţi coloraţi diferit*. Fiecare pereche de pixeli adiacenţi coloraţi diferit contribuie o singura dată (nu de două ori) la costul total pentru pixelii adiacenţi coloraţi diferit.
Baftă!

h2. Date de intrare

Fişierul de intrare $pixels.in$ ...

Fişierul de intrare $pixels.in$ conţine pe prima linie $N$, dimensiunea matricii. Apoi urmează $N$ linii cu $N$ valori pe fiecare din ele. Cea de-a $j$-a valoare de pe linia $i$ reprezintă $A{~ij~}$. În acelaşi format urmează $N$ linii cu $N$ valori reprezentând $B{~ij~}$. La final sunt $N * N$ linii cu câte 4 valori pe fiecare linie. Cea de-a $(i - 1) * N + j$ - a linie din acest grup conţine $C{~ij0~}$ $C{~ij1~}$ $C{~ij2~}$ $C{~ij3~}$.

h2. Date de ieşire

În fişierul de ieşire $pixels.out$ ...

În fişierul de ieşire $pixels.out$ trebuie să afişaţi o singură linie care reprezintă plăcerea maximă care poate fi obţinută.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 100$
* $1 ≤ A{~ij~}, B{~ij~}, C{~ijk~} ≤ 100$
* 10% din teste vor avea $N = 4$
* 30% din teste vor acea $N = 10$

h2. Exemplu
table(example). |_. pixels.in |_. pixels.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 2
1 10
2 2
10 1
3 3
0 1 1 0
0 0 1 1
1 53 0 0
1 0 0 53
| 24

|
h3. Explicaţie

...

Plăcerea maximă se obţine colorând
 
Negru Alb
Negru Negru
 
Observaţi că pixelii $(2, 1)$ şi $(2, 2)$ au un cost foarte mare de a fi colorţi diferit, aşa că îi veţi colora le fel, negru fiind opţiunea cea mai bună.

== include(page="template/taskfooter" task_id="pixels") ==

5347