임의의 정수가 쓰여진 \(N × 2\)개의 보도블럭이 격자형태로 놓여 있다.

보도블럭 위를 그냥 걷기에는 너무 심심하기 때문에

밟고 지나간 보도블럭들에 적힌 수의 합을 최대화하고 싶다.

단, 걸음을 걸을 때는 앞으로 한 행씩 나아가야 하고, 칸 안쪽을 정확히 밟아야 한다.

그리고 넘어질 위험이 있으므로 두 다리가 교차되게 걸으면 안 된다.

다시 말해, 연속된 두 행에 있는 오른발이 밟은 칸은 왼발이 밟은 칸보다 왼쪽에 있으면 안 된다.(반대도 마찬가지다.)

위 그림은 \(N = 5\)에서의 잘못된 예시 2가지와 가능한 예시 2가지를 나타내고 있다.

보도블럭에 적힌 정수들이 주어질 때, 밟고 지나간 보도블럭에 적힌 정수들의 합을 최대화하는 프로그램을 작성해보자.

첫 행은 왼발이나 오른발 중 어느 쪽으로 시작해도 무방하며, 좌우 두 칸 중에 아무 칸에서나 출발해도 상관없다.

입력

• 첫 번째 줄에 \(N\)이 주어진다.\((1 ≤ N ≤ 10000)\)
• 두 번째 줄부터 \(N\)개의 줄에 첫 행(첫 걸음을 내딛는 행)부터 마지막 행(걸음이 끝나는 행)까지 왼쪽 칸의 정수와 오른쪽 칸의 정수가 차례대로 주어진다. 주어지는 값은 \(-1000\) 이상 \(1000\) 이하이다.

출력

• 밟고 지나간 보도블럭들에 적힌 정수의 합의 최댓값을 출력한다.

입력 예시 1

4
1 2
2 1
2 1
1 2

출력 예시 1

7