Herd Splitting
면접 대비시간 제한1초메모리 제한1024 MB
N마리의 소 중 일부를 골라 두 무리로 나눠 각 무리의 우유 생산량이 같아지도록 할 때, 그 같은 생산량의 최댓값을 구한다. N은 40 이하다.
문제
Farmer John wants to split his herd of N (1 ≤ N ≤ 40) cows into two herds. The i-th cow gives Mi liters of milk (1 ≤ Mi ≤ 100) per month, and FJ wants to split his cows such that the each of the resulting two herds produces the same amount of milk. Since it might not be possible to construct such an equal partition of the cows, FJ might first choose to remove some of the cows from the herd (as many as he wants) before splitting up the remaining cows into two equal groups. Let T be the total amount of milk produced by one of these two equally producing groups of cows. Your goal is to find the maximum possible value of T.
입력
- Line 1: One integer: N
- Lines 2..N+1: Each line contains one cow's milk production
출력
A single line with a single integer which is the maximum value of T. If there is no way to remove some number of cows and then split the remaining cows into two herds with equal milk production, you should output the number 0.