== include(page="template/taskheader" task_id="parcele1") ==
Bătrân fiind, ţăranul Florea este nevoit să lase terenul său moştenire celor P fii ai săi. Fiecare fiu are doi copii, nepoţi ai lui Florea.
Terenul ţăranului reprezintă o matrice cu N linii şi M coloane numerotate de la 1 la N, respectiv de la 1 la M. Fiecare element al matricei reprezintă câştigul obţinut la cultivarea cu produse agricole. Terenul poate fi împărţit în parcele. Parcela este o succesiune de linii învecinate din matrice. Fiecare parcelă, ce revine unui fiu, trebuie împărţită celor doi nepoţi în loturi. Primul lot este format din primele K coloane ale parcelei, iar al doilea lot din ultimele M-K coloane ale fiecărei parcele. Ţăranul împarte terenul în P parcele, fiecare fiind la rândul ei împărţită în două loturi.
Câştigul unui lot este suma câştigurilor din acea bucată de pământ.
Înţeleptul bătrân Florea doreşte să facă o împărţire cât mai echilibrată între nepoţii săi. El doreşte ca suma diferenţelor dintre câştigurile de pe loturile a doi nepoţi, copii ai aceluiaşi fiu, să fie cât mai mică (diferenţa este considerată în modul, deci un număr pozitiv sau nul).
Bătrân fiind, ţăranul Florea este nevoit să lase terenul său moştenire celor $P$ fii ai săi. Fiecare fiu are doi copii, nepoţi ai lui Florea. Terenul ţăranului reprezintă o matrice cu $N$ linii şi $M$ coloane numerotate de la $1$ la $N$, respectiv de la $1$ la $M$. Fiecare element al matricei reprezintă câştigul obţinut la cultivarea cu produse agricole. Terenul poate fi împărţit în parcele. Parcela este o succesiune de linii învecinate din matrice. Fiecare parcelă, ce revine unui fiu, trebuie împărţită celor doi nepoţi în loturi. Primul lot este format din primele $K$ coloane ale parcelei, iar al doilea lot din ultimele $M$ - $K$ coloane ale fiecărei parcele. Ţăranul împarte terenul în $P$ parcele, fiecare fiind la rândul ei împărţită în două loturi.
Câştigul unui lot este suma câştigurilor din acea bucată de pământ. Înţeleptul bătrân Florea doreşte să facă o împărţire cât mai echilibrată între nepoţii săi. El doreşte ca suma diferenţelor dintre câştigurile de pe loturile a doi nepoţi, copii ai aceluiaşi fiu, să fie cât mai mică (diferenţa este considerată în modul, deci un număr pozitiv sau nul).
h2. Cerinţă
Dându-se configuraţia terenului ţăranului Florea şi câştigul ce poate fi obţinut la cultivarea cu produse agricole, calculaţi suma cerută şi numărul de posibilităţi de a împărţi terenul astfel încât să se obţină această valoare.
h2. Date de intrare
Pe prima linie a fişierului $parcele.in$ se află trei numere naturale N M P (N respectiv M coordonatele terenului ţăranului, P numărul de fii).
Următoarele N linii conţin M valori naturale, reprezentând câştigurile obţinute la cultivare.
Pe prima linie a fişierului $parcele1.in$ se află trei numere naturale $N$ $M$ $P$ ( $N$ respectiv $M$ coordonatele terenului ţăranului, $P$ numărul de fii). Următoarele $N$ linii conţin $M$ valori naturale, reprezentând câştigurile obţinute la cultivare.
h2. Date de ieşire
Prima linie a fişierului parcele.out va conţine valoarea sumei cerute.
Următoarea linie va conţine numărul de posibilităţi pe care le are Florea pentru a realiza împărţirea terenului său astfel încât să asigure acestă valoare minimă.
Prima linie a fişierului $parcele1.out$ va conţine valoarea sumei cerute. Următoarea linie va conţine numărul de posibilităţi pe care le are Florea pentru a realiza împărţirea terenului său astfel încât să asigure acestă valoare minimă.
h2. Restricţii
• 2 < N, M ≤ 20
• 2 ≤ P ≤ N
• Câştigul la cultivare este cel mult 99.
• Câştigul total al unui lot nu poate fi nul.
• Pentru răspunsul corect la prima cerinţă se acordă 70% din punctaj iar pentru răspunsul corect la ambele cerinţe 100% din punctaj.
* {$2 < N, M ≤ 20$}
* {$2 ≤ P ≤ N$}
* Câştigul la cultivare este cel mult {$99$}.
* Câştigul total al unui lot nu poate fi nul.
h2. Exemplu
h3. Explicaţie
Diferenţa minimă este 5.
Sunt cinci soluţii de împărţire a terenului, soluţii care sunt ilustrate în continuare.
Diferenţa minimă este 5. Sunt cinci soluţii de împărţire a terenului, soluţii care sunt ilustrate în continuare.
!problema/parcele1?poza1.bmp!
