!problema/suma3?formula.bmp!

h2. Cerinta
 
Determinati traseul avand suma minima, precum si aceasta suma.
 

h2. Date de intrare

Fisierul de intrare $suma3.in$ ...

Pe prima linie a fisierului de intrare $suma3.in$ se afla doua numere naturale, {$M$} si {$N$}, reprezentand dimensiunile dreptunghiului (acesta va avea $M$ linii si $N$ coloane). Pe urmatoarele $M$ linii sunt scrise cate $N$ numere naturale separate prin cel putin un spatiu.

h2. Date de iesire

In fisierul de iesire $suma3.out$ ...

Pe prima linie a fisierului de iesire $suma3.out$ se va scrie un numar natural, reprezentand suma traseului minim. Pe a doua linie se va descrie traseul minim, adica toate numerele diferite de $0$ din caroiaj, in ordinea in care au fost introduse in suma. Numerele se vor separa prin cel putin un spatiu.

h2. Restrictii

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

* $1 ≤ M, N ≤ 8$
* {$M * N$} va fi intotdeauna numar par
* {$0 ≤ nr{~i,j~} ≤ 100$}, pentru orice $i$ intre $1$ si {$M$}, $j$ intre $1$ si {$N$}
* Intotdeauna va fi posibil sa se parcurga toate numerele

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

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

|3 4
1 0 10 0
4 3  0 8
0 0  2 0
|70
10 8 2 3 4 1

|
h3. Explicatie

...

{$1 * 10 + 2 * 8 + 3 * 2 + 4 * 3 + 5 * 4 + 6 * 1 = 10 + 16 + 6 + 12 + 20 + 6 = 70$}.

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