Informatica Online Judge

  민제의 염전 체험 [2407 / 0967]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 9   Total Tried : 9


The Champion of this Problem (C++) : gs17018 - ms / 810byte
My Best Submission (C++) : N/A

[35th 김민성]
Writer ID : [gs17013]

Background

방학을 맞은 민제는 나무를 팔아 번 돈으로 전국일주를 떠났다.

기분 좋게 여행을 마무리할 때즈음 민제는 마지막 일정을 위하여 동현이의 염전을 방문하였다.

동현이의 염전은 이곳에서 직접 얻은 소금을 집에 가져갈 수 있는 염전 체험을 운영하고 있다.

염전은 3×n 직사각형 모양으로 생겼고, 민제는 소금을 밀면서 가장 왼쪽 위인 1행 1열 칸에서 가장 오른쪽 아래인 3행 n열 칸까지 이동할 것이다.

민제는 각 i행 j열 칸에 도달했을 때마다 이미 측정된 일정량의 소금 Sij를 얻거나 잃는다. ( Sij < 0인경우 소금을 잃는다 )

동현이의 마인드는 몹시 짜기 때문에 민제가 소금을 얻을 수 있는 칸만 방문하는 것을 원치 않는다.

따라서 이동하면서 이미 방문한 칸은 다시는 방문할 수 없게 하였다.

민제는 NYPC에서 상금을 받지 못해서 염전 체험에서 최대한 많은 소금을 챙겨가고 싶어 한다.

과연 소금을 얼마나 챙겨갈 수 있을까?

Input

첫째 줄에 n (1≤n≤100,000)이 주어진다.

다음 세 줄에는 Sij (-1,000,000,000≤Sij≤1,000,000,000 ) 가 주어진다.

즉, 염전의 i번째 줄의 j번째 수에서는 Sij만큼의 소금을 얻을 수 있다.

Output

1행 1열 칸에서 시작하여 3행 n열 칸까지 이동하면서 얻을 수 있는 소금의 최대치를 출력한다.

이때, 어떠한 칸도 두 번 이상 방문할 수 없다.

IO Example

입력 1
3
1 1 1
1 -1 1
1 1 1

출력 1
7

입력 2
5
10 10 10 -1 -1
-1 10 10 10 10
-1 10 10 10 10

출력 2
110

설명


Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]