3266 Cow School

原文

時間制限:2000ミリ秒
メモリ制限:65536KB

問題

ベッシーは学校に通っており、勉強はよくできる。彼女は N (1 ≦ N ≦ 5000, ただし 1 ケースのみ 1 ≦ N ≦ 50,000) 個のテストを受け、その点数を記録した。 i 番目のテストについて P_i 満点のところ T_i 点をとったという情報がこの問題の入力である。ただし 0 ≦ T_i ≦ P_i ＜ 40,000 かつ 0 ＜ P_i である。

彼女を教えている先生はベッシーの最終的な成績を決定する前に、得点率(T_i / P_i)の低い D 個のテストを除くことにする。ここで彼女の最終的な成績とは、除かれなかったすべてのテストにおける獲得点数の合計を満点の合計で割ったものである。ベッシーは数学が得意なので、この方法が彼女にとってあまり有益ではないことに気づいた。

彼女の主張を示すために、ベッシーは次のような条件を満たす D の値をすべて求めたい: 適切に D 個のテストを選んで除くことで、先生の方法によって得られるであろう最終的な成績よりも良い成績をとることができる。このような D の値をすべて求める手伝いをしてほしい。

ところで、驚くべきことに、ベッシーによれば彼女はどの 2 つのテストの得点率も同じではないという。

入力

1 行目: ひとつの整数 N が書かれている
2 行目から N+1 行目: i+1 行目には 2 つの整数 T_i と P_i が半角空白区切りで書かれている

出力

1 行目: ひとつの整数 K (0 ≦ K ≦ N) を出力せよ。これはベッシーが適切に D 個のテストを選んで除くことで、先生の方法よりも高い成績が得られるような D の値の個数を表す。
2 行目から K+1 行目: 条件を満たすような D の値を 1 行につき 1 つずつ、昇順で出力せよ。

入力例

5
1 2
5 9
3 8
4 10
1 3

出力例

2
1
2

出典

USACO 2007 January Gold