/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
高橋君は料理 1 から N の N 品の料理を作ろうとしています。
料理 i はオーブンを連続した T_i 分間使うことで作れます。1 つのオーブンを 2 つ以上の料理のために同時に使うことはできません。
2 つのオーブンを使えるとき、N 品の料理を全て作るまでに最短で何分かかりますか？ なお、オーブンを使う時間以外は無視できるものとします。
制約
- 1 \leq N \leq 100
- 1 \leq T_i \leq 10^3
- 入力に含まれる値は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
N T_1 \ldots T_N
出力
答えを出力せよ。
入力例 1
5 8 3 7 2 5
出力例 1
13
例えば 2 つのオーブンを次のように使うことで、13 分で全ての料理を作ることができます。
- 1 つ目のオーブン：料理 5,1 を順に作る。
- 2 つ目のオーブン：料理 2,4,3 を順に作る。
入力例 2
2 1000 1
出力例 2
1000
入力例 3
9 3 14 15 9 26 5 35 89 79
出力例 3
138
Score : 400 points
Problem Statement
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.
Constraints
- 1 \leq N \leq 100
- 1 \leq T_i \leq 10^3
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N T_1 \ldots T_N
Output
Print the answer.
Sample Input 1
5 8 3 7 2 5
Sample Output 1
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 Input 2
2 1000 1
Sample Output 2
1000
Sample Input 3
9 3 14 15 9 26 5 35 89 79
Sample Output 3
138