농부 존의 소들은 달 위로 점프를 하고 싶다. 그러나 그들은 점프를 할 수 없다. 농부 존이 사는 지역의 마법사들은 그들이 점프를 할 수 있도록 마법약을 섞어서 P (1 ≤ P ≤ 150,000)개를 만들었다. 이 약들은 조제한 순서대로 처방하여야 하나 어떤 것들은 건너 뛸수도 있다.

이 약은 소들의 점프 능력 S(1 ≤ S ≤ 500)를 가질 수 있게 한다. 홀수 번째로 먹는 약은 점프력이 증가하고 , 짝수 번째는 점프력이 감소한다. 약을 먹기 전의 소들의 점프력은 0 이다.

똑같은 약을 두 번 먹을 수 없으며, 어떤 약을 먹었을 경우, 한 물약당 정해진 점프 능력에 따라 점프한 높이가 감소하거나 증가한다. 몇 개의 물약은 건너뛸 수 있다.

가장 높이 점프할 수 있는 높이를 구하여라.

입력

출력

입출력 예

입력 

8 
7 
2 
1 
8 
4 
3 
5 
6 

출력 

17 

보충 설명

8 개수  
7   -- 먹고 + 
2 
1   -- 먹고 - 
8   -- 먹고 + 
4   
3   -- 먹고 - 
5 
6   -- 먹으면 + 

해서 답은 17 

출처:USACO 2003 U S Open Orange
번역:tncks0121(박수찬)