Nooverlap

Fie o matrice cu $5$ linii și $N$ coloane ce memorează numere întregi și un număr natural nenul $K$.

Cerință

Să se determine suma maximă care se poate obține alegând exact $K$ submatrici $2 \times 2$ care nu se suprapun și însumând elementele din cele $K$ submatrici alese.

Date de intrare

Fişierul de intrare nooverlap.in conține pe prima linie numerele naturale $N$ și $K$ separate prin spațiu.
Următoarele $5$ linii conțin fiecare câte $N$ numere întregi separate prin câte un spațiu.

Date de ieșire

Fişierul de ieşire nooverlap.out va conține pe prima linie un singur număr natural reprezentând suma maximă cerută.

Restricții și precizări

• $2 \leq N \leq 10 \ 000$
• $1 \leq K \leq 100$
• $−1 \ 000 \leq$ valorile din matrice $\leq 1 \ 000$
• O matrice $2 \times 2$ aleasă nu se poate suprapune cu o alta aleasă anterior și de asemenea trebuie să fie complet în interiorul matricii $5 \times N$.
• Se garantează că pentru toate testele se pot alege $K$ submatrici care nu se suprapun.

Exemplu

nooverlap.in

6 3
9 3 1 1 2 4
2 8 1 8 9 -1
0 0 0 -1 8 0
6 7 1 1 2 3
4 5 1 1 1 1

nooverlap.out

68

Explicație

Matricea dată are $5$ linii și $6$ coloane și trebuie să alegem $3$ submatrici $2 \times 2$ care nu se suprapun.
Prima submatrice aleasă:
$9 \ 3$
$2 \ 8$
A doua:
$6 \ 7$
$4 \ 5$
A treia:
$8 \ 9$
$-1 \ 8$
Suma totală va fi $22 + 22 + 24 = 68$.