Contest Duration: - (local time) (100 minutes) Back to Home
D - Cooking /

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

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


• 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


### 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