Trobojnica

면접 대비

시간 제한4초메모리 제한1024 MB

요약

각 열에서 위는 빨강, 가운데는 흰색, 아래는 파랑이 되도록 두 경계를 정해 선호도 합을 최대로 만들고, 모든 열의 합을 구한다.

난이도: 보통10점 중 6점
유형: 동적 계획법, 누적 합, 구현, 배열
정답자: 아직 제출이 없습니다

문제

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.

예제3

예제 1
입력
```
3 1
2
2
2
4
4
4
1
1
1
```
예상 출력
```
7
```

예제 2

입력

5 3
4 4 2
2 3 1
3 2 1000
0 1000 5
7 2 5
100 256 126
783 144 231
45 12 65
189 132 43
126 672 90
67 12 54
14 63 78
24 73 26
37 85 62
43 25 39

예상 출력

예제 3

입력

예상 출력