Doprogramovanie do: 24. august 2020 23:59
10 dní
Popisy už neodovzdávajte. Ešte stále však môžete odosielať vaše programy, za ktoré dostanete časť bodov.
Počet bodov:
Popis:  12b
Program:  8b

Mesto je v karanténe. Všetci sú doma odizolovaní a odlúčení od akejkoľvek ľudskej interakcie. Obyvatelia už dva mesiace nevideli žiaden úsmev, lebo všetky tváre sú zahalené v rúškach. Počasie je ponuré, doma niet čo robiť. Všetci sú v depresii.

Mestská správa však nestráca nádej a rozhodla sa s tým niečo urobiť. Obyvateľstvo by určite rozveselilo trocha motivačnej hudby z rádia. V meste však nie je vysielač, tak treba nejaký postaviť.

Avšak so zvyšujúcou sa vzdialenosťou od vysielača sa zhoršuje signál, a zvyšuje depresia. Presnejšie depresia každého občana je rovná druhej mocnine jeho vzdialenosti od vysielača v metroch.

Aby sa signál mohol lepšie šíriť do všetkých strán a nestáli mu v ceste budovy rozhodli sa ho postaviť na križovatke. Ktorá križovatka však bude najvhodnejšia?

Úloha

Mesto má tvar štvorcovej siete o rozmeroch \(r \times s\). Políčka sú štvorcové pozemky s dĺžkou strany \(8\) metrov. Každý pozemok má súradnice \((i,j)\), je na ňom jeden dom a žije v ňom \(c_{i j}\) ľudí. Pre zjednodušenie predpokladáme, že všetci ľudia sa nachádzajú presne v strede pozemku na ktorom bývajú. V severozápadnom rohu mesta je pozemok so súradnicami \((1,1)\) a v juhovýchodnom \((r,s)\). Medzi pozemkami vedú ulice, ich šírku môžeme zanedbať. Tieto ulice sa pretínajú v \((r + 1) \times (s + 1)\) križovatkách. V severozápadnom rohu mesta je križovatka so súradnicami \((0,0)\), v juhovýchodnom \((r,s)\).

Zistite na ktorej križovatke má mesto postaviť vysielač aby celková depresia jeho obyvateľstva bola najmenšia možná.

Formát vstupu

Na prvom riadku sú dve celé čísla \(r\) a \(s\), oddelené medzerou - rozmery mesta. Platí \(1 \leq r,s \leq 1\,000\) Nasleduje \(r\) riadkov, každý z nich obsahuje \(s\) celých čísel oddelených medzerou. V \(i\)-tom riadku a \(j\)-tom stĺpci je číslo \(c_{i j}\), počet obyvateľov domu na súradniciach \((i,j)\). Platí \(0 \leq c_{i j} \leq 100\,000\).

Je osem testovacích sád. V sadách 1 a 2 naviac platí \(r,s \leq 30\), a v sadách 3, 4 a 5 platí \(r,s \leq 200\).

Formát výstupu

Na prvý riadok vypíšte jedno číslo; najmenšiu dosiahnuteľnú depresiu. Na druhý riadok vypíšte súradnice vysielača, ktoré túto hodnotu dosiahnu. Ak existuje viac riešení vypíšte ľubovoľné z nich.

Výsledok sa nemusí zmestiť do klasickej 32 bitovej číselnej premennej (v C++ preto použite premennú typu long long).

Príklady

Input:

2 3
1 2 2
2 9 1

Output:

928
1 1

Optimálne je tiež aj \((1,2)\). \(928\) sme dostali ako \(32\cdot(1+2+2+9)+160\cdot(2+1)\)

Input:

4 4
0 0 0 2
1 2 5 3
2 0 1 4
1 1 0 0

Output:

2880
2 2

Odovzdávanie

Na odovzdávanie sa musíš prihlásiť

Otázky a diskusia

Po skončení kola budete mať príležitosť na diskutovanie o riešeniach v diskusii pod vzorovým riešením.