1

図：下にあるダンボールは上にあるダンボール以上の重さでなければならない

N
w_1
w_2
:
:
w_N

• 入力は $N+1$ 行ある。
• $1$ 行目には、ダンボールの個数を表す整数 $N(1≦N≦50)$ が与えられる。
• $2$ 行目からの $N$ 行には、$i+1(1≦i≦N)$ 行目に $i$ 番目に運ぶダンボールの重さを表す整数 $w_i(1≦w_i≦100,000)$ が与えられる。

1

5
4
3
1
2
1

2

• 下図の例の順に積み重ねると、$2$ つのダンボールの山ができる。
• $3$ 番目のダンボールの次に重さ $2$ のダンボールをその上に重ねることはできないので $1$ つの山にすることはできず、最小は $2$ となる。

7
93
249
150
958
442
391
25

3

• 下図の形に積み重ねると、山の数は $3$ となる。

4
100
100
100
100

1

• 同じ重さのダンボールは積み重ねられるので、$1$ つの山にすることができる。

6
5
10
15
20
25
30

6

• どのダンボールも前に運んだダンボールの上に重ねられないので、$1$ つも積み重ねることができない。
• したがって、$6$ つの山が最小となる。

15
3
1
4
1
5
9
2
6
5
3
5
8
9
7
9

6

• 下図のように積み重ねると最小となる。