Tekst zadatka

Patrick organizira natjecanje u šahu. Na natjecanju se nadmeću šahisti iz dvije škole. Svakom šahistu je pridružen broj koji predstavlja njegovu jačinu. Također, ukoliko \(i\)-ti šahist iz prve škole igra protiv \(j\)-tog šahista iz druge škole, zabava publike će se povećati za \(x_{ij}\).

Međutim, publika je izbirljiva. Ako su pogledali meč u kojem je igrao igrač jačine \(r\), nakon toga žele gledati isključivo mečeve u kojima su šahisti iz te škole veće jačine od \(r\).

Patricka zanima kolika je najveća ukupna zabava publike koju može postići odabirom valjanog niza mečeva.

Napomena: Nije nužno da svaki šahist igra meč, pa je moguće da ni jedan meč ne bude odigran ako to maksimizira zabavu publike (tada je zabava jednaka \(0\)).

Ulazni format

• Prvi redak sadrži jedan cijeli broj \(n\) (\(1 \leq n \leq 1000\)) — broj šahista u svakoj školi.
• Drugi redak sadrži \(n\) cijelih brojeva \(a_1, a_2, \dots, a_n\) (\(0 \leq a_i \leq 10^9\)) — jačine šahista iz prve škole (sve vrijednosti su različite).
• Treći redak sadrži \(n\) cijelih brojeva \(b_1, b_2, \dots, b_n\) (\(0 \leq b_j \leq 10^9\)) — jačine šahista iz druge škole (sve vrijednosti su različite).
• Četvrti redak je prazan.
• Nakon toga slijedi \(n\) redaka, svaki s \(n\) cijelih brojeva. U \(i\)-tom retku se nalazi \(n\) vrijednosti \(x_{i1}, x_{i2}, \dots, x_{in}\) gdje \(-10^9 \leq x_{ij} \leq 10^9\) — povećanje zabave ako i-ti šahist iz prve škole igra protiv j-tog šahista iz druge škole.

Izlazni format

Ispišite jedan cijeli broj — maksimalnu ukupnu zabavu koju publika može dobiti.

Ograničenja

• Sve jačine šahista su međusobno različite unutar svake škole.
• Vrijednosti zabave mogu biti negativne, pozitivne ili nula.
• Nije dopušteno ponovno gledati šahiste s jednakom ili manjom jačinom nego prethodno gledanima iz iste škole.

Primjer

Ulaz

3
3 1 4
2 6 5

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

Izlaz

15