Trobojnica

문제

Moje zastave uvijek su iste boje... crveno-bijelo-plave.

Fifi voli bojati zastave sa zanimljivim svojstvima. Nakon što je navio alarm za sljedeći dan, odlučio je prije spavanja obojati još jednu zastavu.

Njegova zastava ima visinu $nn$ i širinu $mm$, a polje u $ii$-tom retku i $jj$-tom stupcu ima sklonost $c_{i,j}c\_\{i,j\}$ crvenoj boji, $b_{i,j}b\_\{i,j\}$ bijeloj boji, i $p_{i,j}p\_\{i,j\}$ plavoj boji.

Fifi boja zastavu stupac po stupac: najprije oboji nekoliko polja u crvenu boju, zatim nekoliko u bijelu boju, a ostatak u plavu boju, točno tim redom gledano s vrha stupca prema dnu. Svaki stupac mora imati barem po jedno polje crvene, bijele i plave boje.

Pritom želi maksimizirati ostvarene sklonosti, tj. želi da je sljedeći zbroj najveći mogući:

• Ako je polje u $ii$-tom retku $jj$-tog stupca obojano u crvenu boju, tada se ukupna ostvarena sklonost povećava za $c_{i,j}c\_\{i,j\}$.
• Ako je polje u $ii$-tom retku $jj$-tog stupca obojano u bijelu boju, tada se ukupna ostvarena sklonost povećava za $b_{i,j}b\_\{i,j\}$.
• Ako je polje u $ii$-tom retku $jj$-tog stupca obojano u plavu boju, tada se ukupna ostvarena sklonost povećava za $p_{i,j}p\_\{i,j\}$.

Odredite maksimalnu ostvarenu sklonost.

입력

U prvom retku su prirodni brojevi $nn$ i $mm$ (3 ≤ n ≤ 2\,500, 1 ≤ m ≤ 2\,500), visina i širina zastave.

Slijedi $nn$ redatka po $mm$ cijelih brojeva $c_{i,j}c\_\{i,j\}$ (0 ≤ c_{i,j} ≤ 1\,000), gdje $c_{i,j}c\_\{i,j\}$ predstavlja sklonost crvenoj boji polja u $ii$-tom retku i $jj$-tom stupcu.

Slijedi $nn$ redatka po $mm$ cijelih brojeva $b_{i,j}b\_\{i,j\}$ (0 ≤ b_{i,j} ≤ 1\,000), gdje $b_{i,j}b\_\{i,j\}$ predstavlja sklonost bijeloj boji polja u $ii$-tom retku i $jj$-tom stupcu.

Slijedi $nn$ redatka po $mm$ cijelih brojeva $p_{i,j}p\_\{i,j\}$ (0 ≤ p_{i,j} ≤ 1\,000), gdje $p_{i,j}p\_\{i,j\}$ predstavlja sklonost plavoj boji polja u $ii$-tom retku i $jj$-tom stupcu.

출력

U prvi i jedini redak ispišite traženi broj.

힌트

Pojašnjenja probnih primjera: Lijevo je prikaz bojanja zastave prvog probnom prijema, u sredini drugog probnog prijema, i desno trećeg probnog primjera.

[이미지 1]