Problem D
Balanced Diet
Appreciating the time savings, product consistency and nutritional value of prepared foods, you have decided to eat all your meals from cans. You have a shopping bag full of cans, enough for the next two meals. You want to finish the entire contents of all of these cans within the next two meals, but, since you have no means of refrigeration, you can’t save partial cans from one meal to the next. You need to divide the cans up so you have approximately the same caloric intake for each of the next two meals. If you can’t make it work out exactly, you will choose to eat more calories for your first meal and fewer for your second.
Input
Input contains up to $150$ test cases, one per line. Each test case starts with a positive integer, $1 \leq n \leq 20$, indicating the number of cans in your shopping bag. This is followed by $n$ integer values in the range $[100,600]$, each one representing the calorie value of a particular can. The sequence of test cases ends with a value of zero for $n$.
Output
For every test case, print out a line giving your calorie intake for the next two meals under the optimal partitioning of cans.
| Sample Input 1 | Sample Output 1 |
|---|---|
8 529 382 130 462 223 167 235 529 12 528 129 376 504 543 363 213 138 206 440 504 418 0 |
1344 1313 2181 2181 |
