Zadanie

Intriky s obedom

Počet bodov: 60

Písal sa štvrtok 14. apríla 2017. Kubo sa po dlhom dlhom, namáhavom dni ničnerobenia v škole vrátil domov a, ako zvyčajne, jeho primárnou destináciou bola posteľ. Veľmi rýchly dvojhodinový powernap bol samozrejme nasledovaný útokom na chladničku. Ten bol však veľmi neúspešný, keďže tá bola úplne prázdna. V tomto bode by iní padli do hlbokej depresie. Kubo, ako pravý obchodník ale vie z každej situácie vyťažiť najviac. A tak si uvedomil, že konečne má výhovorku pre rodičov, prečo musel objednávať jedlo. (táto výhovorka mu samozrejme neprešla, ale to je príbeh na iný deň…)

Otvoril si stránku Hofera a začal si prezerať denné menu, keď mu zrazu napadol ďaľší, ešte diabolskejší nápad. Konečne sa pomstí svojmu bratovi Filipovi za to, že mu na poslednej grilovačke zjedol všetkú slaninu! Uvedomil si totiž, že jeho brat Filip sa ešte stále nevrátil domov. Osudová chyba. Keď už Kubo objednáva jedlo, musí samozrejme už niečo objednať aj jemu, inak by manéver na rodičov nezafungoval (…). Avšak kto mu dokáže, že sebe objedná oveľa lepšie jedlo než Filipovi?

A o pár momentov jeho genialita udrela opäť. Však on môže jedlá v objednaných menu aj povymieňať!

Úloha

V Hoferi majú \(n\) denných menu. Každé sa skladá z polievky, hlavného jedla, dezertu a nápoja. Každé z jedál (vrátane nápoja) má istú chutnosť.

Kubo objedná dve (nie nutne rôzne) menu. Následne jedlá v nich prerozdelí medzi seba a Filipa, tak, že každému z nich zostane práve jedno jedlo každého typu.

Chutnosť obeda si definujme ako súčet chutností jedál, ktoré daná osoba dostane. Zistite maximálny možný rozdiel chutnosti Kubovho a Filipovho obeda.

Vstup a Výstup

Na prvom riadku vstupu sa nachádza číslo \(n\) (\(2\leq n \leq 10^5\)).

Na každom z nasledujúcich \(n\) riadkov je štvorica prirodzených čísel \(p, h, d, v\) (\(1 \leq p,h,d,v \leq 10^8\)). Tie označujú postupne chutnosť polievky, hlavného jedla, dezertu a nápoja v danom menu.

Vypíšte jedno celé číslo - maximálny rozdiel súčtov chutností svojích a Filipových jedál, ktorý vie Kubo dosiahnuť.

V prvej sade \(n \leq 1000\). V ďalších troch bude výrazne väčšie.

Príklad

Input:

3
8 6 3 1
7 5 3 2
1 4 5 6

Output:

16

Kubo objedná prvé a tretie menu. Z prvého si nechá polievku a hlavné jedlo, z druhého dezert a nápoj. Jeho obed bude tak mať chutnosť \(8+6+5+6=25\) a Filipov \(1+4+3+1=9\).