던전 timer 2s memory 1024MB

철수와 영희는 게임을 하는 도중 던전을 통과하게 되었다. 던전은 가로 N칸, 세로 N칸인 격자 모양이다.

격자의 행들은 위에서부터 0부터 N − 1까지 번호가 붙어져 있으며, 격자의 열들은 왼쪽부터 0부터 N − 1 까지 번호가 붙어져 있다. i번 행, j번 열에 위치한 칸을 칸 (i, j)라고 부른다. 

던전을 통과하는 규칙은 아래와 같다. 

• 철수는 던전의 제일 왼쪽 위 칸에서 출발하여 제일 오른쪽 아래 칸으로 이동한다. 이동할 때, 철수는 현재 위치한 칸에서 오른쪽 혹은 아래로 바로 인접한 칸으로만 이동이 가능하다. 

• 영희는 던전의 제일 오른쪽 위 칸에서 출발하여 제일 왼쪽 아래 칸으로 이동한다. 이동할 때, 영희는 현재 위치한 칸에서 왼쪽 혹은 아래로 바로 인접한 칸으로만 이동이 가능하다. 

던전의 각 칸에는 아이템이 하나씩 있다. 각 아이템의 가치는 양의 정수, 0, 혹은 음의 정수이며, 칸 (i, j) 에 있는 아이템의 가치는 V [i][j]이다. 철수와 영희는 모든 칸에 있는 아이템의 가치를 이미 다 알고 있다. 던전을 통과하고 나면 철수와 영희가 지나간 모든 칸의 아이템들을 다 모으게 된다. 두 사람이 모두 지나간 칸에서도 아이템은 하나만 모으게 된다는 것에 주의하라. 철수와 영희가 모으는 아이템 가치 합의 가능한 최댓값을 구하는 프로그램을 작성하라.

제약 조건

• 2 ≤ N ≤ 1 000 

• 모든 i, j에 대해 −100 000 ≤ V [i][j] ≤ 100 000 (0 ≤ i, j ≤ N − 1)​