5663: ABC204 —— D - Cooking
[Creator : ]
Description
Takahashi is going to cook $N$ dishes called Dish $1$ through $N$.
Dish $i$ can be cooked by using an oven for $T_i$ consecutive minutes. An oven cannot be used for two or more dishes simultaneously.
If Takahashi has two ovens to use, what is the shortest number of minutes needed to cook all the $N$ dishes? Assume that all processes other than using ovens take negligible time.
Dish $i$ can be cooked by using an oven for $T_i$ consecutive minutes. An oven cannot be used for two or more dishes simultaneously.
If Takahashi has two ovens to use, what is the shortest number of minutes needed to cook all the $N$ dishes? Assume that all processes other than using ovens take negligible time.
Input
Input is given from Standard Input in the following format:
$N$
$T_1\ T_2\ \dots\ T_N$
$N$
$T_1\ T_2\ \dots\ T_N$
Output
Print the answer.
Constraints
$1≤N≤100$
$1≤T_i≤10^3$
All values in input are integers.
$1≤T_i≤10^3$
All values in input are integers.
Sample 1 Input
5
8 3 7 2 5
Sample 1 Output
13
We can, for example, use the two ovens as follows to cook all the dishes in $13$ minutes.
- The first oven: Cook Dishes $5$ and $1$ in this order.
- The second oven: Cook Dishes $2,\ 4$, and $3$ in this order.
Sample 2 Input
2
1000 1
Sample 2 Output
1000
Sample 3 Input
9
3 14 15 9 26 5 35 89 79
Sample 3 Output
138
HINT
相同题目:ABC204。