Alice i Bob otišli su na Filipine gdje su zatekli djecu kako igraju Bato Bato Pik. Budući da su i oni htjeli biti dio zabave, odlučili su istražiti što je to Bato Bato Pik. Na Wikipediji piše da je to samo Kamen-Papir-Škare na jeziku Togalog, što oni već znaju igrati. No na Wikipediji uz Kamen-Papir-Škare stoji Kamen-Papir-Škare-Gušter-Spock, unaprijeđena verzija igre, a uz nju stoji Kamen-Papir-Škare-Vatra-Zrak-Zmija-Čovjek-Stablo-Vuk-Zmaj-Voda-... itd.

Neki od tih naziva i pravila im se ne sviđaju te žele napraviti svoju igru, stoga će ju napraviti na sljedeći način:

Alice i Bob su se dogovorili da će njihova igra imati \(n\) stvari. Alice može svoju \(i\)-tu stvar pokazati \(a_i\) puta, a Bob \(i\)-tu stvar može pokazati \(b_i\) puta. Kako bi igra bila poštena vrijedit će \(\sum a_i = \sum b_i\).

Zatim su se Alice i Bob dogovorili koji predmet pobjeđuje kojeg. Ta pravila su dana u obliku matrice \(M\) koja je veličine \(n \times n\). Ako je element \(M_{ij}\) jednak 1, onda stvar \(i\) pobjeđuje stvar \(j\) i bod dobiva tko je god u tom potezu stavio stvar \(i\). Ako je element \(M_{ij}\) jednak -1, onda stvar \(i\) gubi protiv stvari \(j\) te bod dobiva onaj tko je pokazao \(j\). Ukoliko je \(M_{ij}\) jednak 0, onda je neriješeno između \(i\) i \(j\). Kako bi igra imama smisla matrica \(M\) će uvijek biti antisimetrična.

Sada kad su se Alice i Bob napokon dogovorili oko svih pravila, Alice zanima koliko najviše može skupiti bodova i koliko najmanje bodova može skupiti ako u oba slučaja Alice i Bob surađuju.

Ulaz

U prvom retku se nalazi broj \(n\), (\(1 \leq n \leq 300)\), broj stvari koje Alice i Bob mogu pokazati.

U sljedećem retku se nalazi \(n\) brojeva \(a_i\), (\(0 \leq a_i \leq 10^{16}\)), koliko puta Alice može pokazati koju stvar.

U još jednom retku se nalazi \(n\) brojeva \(b_i\), (\(0 \leq b_i \leq 10^{16},\)), koliko puta Bob može pokazati koju stvar.

Zatim slijedi \(n\) redataka svaki sa po \(n\) brojeva, odnosno matrica \(M\) dimenzije \(n\times n\). Svaki element matrice je -1, 0 ili 1.

Uvijek će vrijedit \(\sum\limits_{i=1}^n a_i = \sum\limits_{i=1}^n b_i\) te \(M_{ij} = - M_{ji}\).

Izlaz

U jedan red ispišite dva broja, prvi broj je koliko Alice može najviše bodova sakupit, a drugi broj koliko najmanje.

Podzadatci

Ulaz primjera 1

3
1 2 3
2 1 3
0 -1 1
1 0 -1
-1 1 0

Izlaz primjera 1

4 0