28712번 - 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 $n$ i širinu $m,ドル a polje u $i$-tom retku i $j$-tom stupcu ima sklonost $c_{i,j}$ crvenoj boji, $b_{i,j}$ bijeloj boji, i $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 $i$-tom retku $j$-tog stupca obojano u crvenu boju, tada se ukupna ostvarena sklonost povećava za $c_{i,j}$.
• Ako je polje u $i$-tom retku $j$-tog stupca obojano u bijelu boju, tada se ukupna ostvarena sklonost povećava za $b_{i,j}$.
• Ako je polje u $i$-tom retku $j$-tog stupca obojano u plavu boju, tada se ukupna ostvarena sklonost povećava za $p_{i,j}$.

Odredite maksimalnu ostvarenu sklonost.

입력

U prvom retku su prirodni brojevi $n$ i $m$ (3ドル ≤ n ≤ 2,500円,ドル 1ドル ≤ m ≤ 2,500円$), visina i širina zastave.

Slijedi $n$ redatka po $m$ cijelih brojeva $c_{i,j}$ (0ドル ≤ c_{i,j} ≤ 1,000円$), gdje $c_{i,j}$ predstavlja sklonost crvenoj boji polja u $i$-tom retku i $j$-tom stupcu.

Slijedi $n$ redatka po $m$ cijelih brojeva $b_{i,j}$ (0ドル ≤ b_{i,j} ≤ 1,000円$), gdje $b_{i,j}$ predstavlja sklonost bijeloj boji polja u $i$-tom retku i $j$-tom stupcu.

Slijedi $n$ redatka po $m$ cijelih brojeva $p_{i,j}$ (0ドル ≤ p_{i,j} ≤ 1,000円$), gdje $p_{i,j}$ predstavlja sklonost plavoj boji polja u $i$-tom retku i $j$-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.