XOINC - A Coin Game

Những con bò của Farmer John thích chơi những trò chơi liên quan đến tiền nên FJ mời chúng chơi 1 trò chơi mới gồm 2 người gọi là Xoinc.

Cho 1 ngăn xếp có N đồng tiền (5 <= N <= 2000). Đồng thứ i chứa 1 số nguyên Ci là giá trị của đồng xu đó (1 <= Ci <= 100000).

Người chơi 1 bắt đầu trò chơi bằng cách lấy từ ngăn xếp 1 hoặc 2 đồng tiền (C1 hoặc C1 + C2). Nếu người đầu tiên chỉ lấy 1 đồng, người thứ 2 có thể lấy 1 hoặc 2 đồng tiền trong lượt tiếp theo. Nếu người thứ nhất lấy 2 đồng tiền thì người thứ 2 có thể lấy tiếp 1, 2, 3 hoặc 4 đồng tiền tiếp theo từ ngăn xếp. Trong mỗi lượt chơi, người chơi phải lấy ra ít nhất 1 đồng và tối đa là gấp đôi số đồng tiền mà người kia đã lấy ở lượt chơi trước đó. Trò chơi kết thúc khi ngăn xếp không còn đồng tiền nào.

Mục tiêu của mỗi người chơi là lấy được những đồng tiền sao cho tổng giá trị của chúng là lớn nhất có thể. Coi người thứ 2 luôn chơi tối ưu, số tiền tối đa mà người chơi thứ nhất có thể đạt được sau khi trò chơi kết thúc là bao nhiêu?

 

Input

Dòng 1: 1 số nguyên N

Dòng 2..N+1: Dòng i+1 chứa 1 số nguyên Ci

Output

1 số nguyên duy nhất là giá trị tối đa mà người chơi thứ nhất có thể đạt được.

Example

Input:

5
1
3
1
7
2

Output:
9

 

Giải thích:

Người chơi 1 bắt đầu bằng cách lấy đồng tiền 1 (giá trị là 1). Người chơi 2 sẽ lấy 1 đồng tiền tiếp theo (giá trị là 3). Người chơi thứ nhất tiếp tục lấy 2 đồng tiền (giá trị 1 và giá trị 7). Người thứ 2 lấy nốt đồng tiền còn lại (giá trị 2). Kết thúc trò chơi, người 1 sẽ bốc được tối đa là: 1 + 1 + 7 = 9


Được gửi lên bởi:HNUE
Ngày:2009-11-12
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU NODEJS OBJC PERL6 PYPY RUST SED SQLITE VB.NET
Nguồn bài:USACO NOV09 Silver Division

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.