Cinema tickets
In this task, you are invited to help a cashier to sell the movie tickets. There are two free rows, one after another, with m places in each. The seats in each row are numbered from left to right by numbers from 1 to m. The people are standing in the queue in groups by a[i] people. Each group can be put in one of the rows in a row, or, if a[i] is even, you can put it in two rows in places with the same numbers.
The cashier is thoughtful: will he be able to put all the groups in compliance with these requirements? Help him to find the minimum length of the row m, into which it is possible to sit all the groups, observing the constraints.
Input
The first line contains the number of groups n (1 ≤ n ≤ 1000). Second line contains n integers a[1], a[2], ..., a[n], where a[i] is the number of people in the i-th group. The sum of all a[i] is no more than 10^5.
Output
Print one number - the minimum length of one row, at which it will be possible to sit all n groups.