PC 重ね Scala編（paizaランク A 相当）

問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！

問題

下記の問題をプログラミングしてみよう！

paiza くんは、同じサイズのノート PC をたくさん持っていますが、それらを収納するスペースがありません。
i 番目の PC の重さは w_i であり、上に乗っている重量が耐荷重量 r_i よりも大きくなった場合壊れてしまいます。
どの PC も壊れないようにしながら、できるだけスペースを取らないように全ての PC を収納したいです。
そこで paiza くんは床に PC 数台分のスペースをとり、そこに PC を重ねて収納することにしました。
床にとるスペースが最小になるように収納した場合、PC 何台分のスペースが必要になるかを求めてください。

例として、入力例 1 の 3 台の PC は以下の通り PC 1 台分のスペースに重ねて収納することができるので、この場合は 1 を出力してください。

入力される値

n
w_1 r_1
w_2 r_2
...
w_n r_n

・1 行目では paiza くんが持っている PC の台数 n が整数で与えられます。
・続く n 行のうち i 行目では、i 行目の PC の重量 w_i と耐荷重量 r_i が半角スペース区切りで与えられます。

入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。標準入力からの値取得方法はこちらをご確認ください

期待する出力: ・できるだけ小さいスペースで収納をおこなった時、pc 何台分のスペースが必要になるかを 1 行で出力してください。
・また、末尾に改行を入れ、余計な文字、空行を含んではいけません。

条件: すべてのテストケースにおいて、以下の条件をみたします。

・1 ≦ n ≦ 10
・1 ≦ w_i ≦ 100,000
・1 ≦ r_i ≦ 100,000

入力例1: 3
1 3
2 3
3 3

出力例1: 1

入力例2: 3
1 3
2 2
3 1

出力例2: 2

入力例3: 4
10 10
10 10
10 10
10 10

出力例3: 2

入力例4: 3
5 1
200 8
3 150

出力例4: 1

問題一覧へ戻る