Cinema tickets#5463

Cinema tickets

1 second

128 megabytes

Medium

You are asked to help a cashier sell movie tickets. There are two consecutive free rows, each with $m$ seats. The seats in each row are numbered from left to right, from $1$ to $m$ . People are standing in line in groups of $a_{i}$ a_i people. Each group can be seated consecutively in any one row, or, if $a_{i}$ a_i is even, the group can be split and seated in both rows in places with the same numbers.

The cashier is pondering: is it possible to seat all the groups according to these requirements? Help them by finding the minimum length $m$ of a row such that it is possible to seat all the groups while observing the constraints.

\InputFileThe first line contains the number of groups $n$ ( $1 \leq n \leq 1000$ 1 \le n \le 1000). The second line contains $n$ integers $a_{1}, a_{2}, \dots, a_{n}$ a_1, a_2, \ldots, a_n, where $a_{i}$ a_i is the number of people in the $i$ -th group. The sum of all $a_{i}$ a_i does not exceed $1 0^{5}$ 10^5.

\OutputFilePrint a single integer — the minimum possible length of one row $m$ such that all $n$ groups can be seated as required.

Examples

Example 1

Loading

Example 2

Loading

a_{i}

a_{i}

1 \leq n \leq 1000

a_{1}, a_{2}, \dots, a_{n}

a_{i}

a_{i}

1 0^{5}