보석을 세공해서 모아놓은 N×N의 칸이 있는 판이 있다. (1 <= N <= 200) 각 칸에는 보석들 이 들어있지만, 세공이 실패한 보석들의 위 치에는 모조품으로 채워져있다. 좋은 보석일 수록 판의 가치를 더 많이 올려주고, 모조품 은 전체적인 판의 가치를 떨어뜨리게 된다. 유독 시력만 좋은 보석털이범 난쿤이는 보석 의 가치를 한 눈에 보고 보석과 모조품을 구 분할 수 있으며 그 가치를 숫자로 매길 수 있다.
| -34 | 24 | 16 | 40 | 18 |
| 46 | 20 | 49 | -22 | -47 |
| -47 | -5 | -17 | 49 | -33 |
| -11 | -14 | 45 | 42 | -9 |
| 18 | 25 | -27 | 48 | 39 |
다음은 돈독이 오른 난쿤이의 눈에 보이는 보석들이다. 판을 조각내면 들고 이동하기 어렵기 때문에, 직사각형의 형태로 잘려진 가치가 가장 높게 잘라서 들고 도망을 가려 한다. 다음과 같은 판을 해당 모양으로 자르 면 273의 가치로 가장 높게 챙길 수 있다.
| -34 | 24 | 16 | 40 | 18 |
| 46 | 20 | 49 | -22 | -47 |
| -47 | -5 | -17 | 49 | -33 |
| -11 | -14 | 45 | 42 | -9 |
| 18 | 25 | -27 | 48 | 39 |
여러분은 난쿤이를 도와서 해당 판을 잘라서 만들 수 있는 가장 높은 가치를 출력해주면 된다. 숫자들은 -100 이상 100 이하의 숫자 이다.
입력 5 -34 24 16 40 18 46 20 49 -22 -47 -47 -5 -17 49 -33 -11 -14 45 42 -9 18 25 -27 48 39 출력 273
출처:algolab.org