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 ai people. Each group can be put in one of the rows in a row, or, if ai 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 a1, a2, ..., an, where ai is the number of people in the i-th group. The sum of all ai is no more than 105.

Output

Print one number - the minimum length of one row, at which it will be possible to sit all n groups.