점수 님
시간 제한2초메모리 제한512 MB
모든 더미가 크기 1이 될 때까지 더미를 둘로 나누며 색을 칠할 때, 최적으로 플레이하는 앨리스가 얻는 흰 돌의 수를 구한다.
문제
Alice와 Bob이 님 비슷한 게임을 하려고 한다.
처음에 돌 더미가 n개 있고, i번째 더미에는 ai개의 돌이 들어 있다. 두 사람은 번갈아 차례를 가지며 Alice가 먼저 둔다. 자기 차례가 되면 돌이 2개 이상 들어 있는 더미 하나를 골라, 각각 돌이 1개 이상 들어 있는 두 개의 새 더미로 나눈다. 그런 다음 새 더미 하나에 든 돌을 전부 흰색으로, 다른 더미에 든 돌을 전부 검은색으로 칠한다. 게임은 모든 더미가 돌 1개만 담을 때까지 이어진다.
게임이 끝난 뒤 Alice의 점수는 판 위에 있는 흰 돌의 개수이고, Bob의 점수는 검은 돌의 개수이다. 두 사람 모두 자기 점수를 최대한 크게 만들려고 최선의 플레이를 할 때, Alice의 점수는 얼마가 되는가?
입력
첫째 줄에 정수 n이 주어진다. (1 ≤ n ≤ 128)
둘째 줄에 n개의 정수 a1, a2, . . . , an이 주어진다. (2 ≤ ai ≤ 128)
돌의 처음 색은 결과에 영향을 주지 않는다.
출력
두 사람이 최선의 플레이를 할 때 Alice의 점수를 정수 하나로 출력한다.
힌트
예제에서는 두 사람이 어떻게 두든 두 더미가 똑같이 나뉜다.