PKU 2181. Jumping Cows

점프하는 소들

Time Limit: 1000MS	Memory Limit: 65536K
Total Submissions: 4560	Accepted: 2761

설명

농부 John의 소들은 동요에 나오는 것 처럼 달을 뛰어넘고 싶어합니다. 그러나 불행하게도 소들은 뛸 수 없습니다.

그 지역에 사는 주술사가 달을 뛰어넘고 싶어하는 소들의 부탁을 들어주기 위해 P (1 <= P <= 150,000) 개의 물약을 만들었습니다. 이 물약들은 조제된 순서대로 투약되는데 개중에 투약되지 않고 다음 물약으로 넘어가는 경우도 있습니다.

각 물약은 소들이 점프할 수 있는 'strength'  (1 <= strength <= 500)를 증가시켜줍니다. 각 소들이 물약을 마시는 순서를 놓고 볼 때, 홀수번째로 먹는 물약은 소의 점프능력을 증가시켜주고; 짝수번째로 먹는 물약은 소의 점프능력을 감소시킵니다. 물약을 먹기 전의 소의 점프능력은 당연히 0입니다.

모든 소는 자신에게 주어진 물약들 중 한 개 이상은 마셔야 합니다. 이 때, 물약의 성능에 따라 마실지 마시지 않을지를 판단하여 다음 물약으로 넘길 수 있고, 한 번 마셨거나 넘긴 물약은 다시 마실 수 없습니다.

어떤 물약을 투여했을 때 가장 높게 점프할 수 있는지를 알아내세요.

입력

* 첫번째 줄: 하나의 양정수 P 

* 두번째 줄부터 P+1번째 줄: 각 줄은 하나의 양정수가 들어가는데, 물약의 strengh 를 의미합니다. 2번째 줄은 첫번째 로 주어진 물약의 strength 이고; 3번째 줄은 두번째로 주어진 물약의 strength 이고; 이하 동일합니다.

출력

* 첫번째 줄: 최대로 점프할 수 있는 하나의 양정수. 

입력 예시

8
7
2
1
8
4
3
5
6

출력 예시

17

Source

USACO 2003 U S Open Orange


p.s: 미친소도 아니고 왜 동요에서 소들이 달로 뛰는거람 도대체..
p.s2: Lonewolf dlbo의 의견을 수렴하여 일부분 수정합니다.