外部サイトへ移動します

リンク先の URL を確認してから開いてください。

別タブで開く

Q - Neko Da!

作成者 nekooooooo、siooisi、jammy、trueryob

テスター nekooooooo、siooisi、tau0529

配点 450 点

実行時間制限
2.2 秒
メモリ制限
222 MiB

問題文

NN 匹のねこがいます。

ねこ ii からは、ちょうどAiA_i回撫でることで幸福を得られます。 ただし、撫でる回数には注意が必要です。

  • ねこ ii を撫でるたびに、あなたに対するねこからの反感度が 11 増加します。
  • ねこの反感度が BiB_i に達すると、そのねこに嫌われ、あなたはがっくりしてしまいます。
  • ねこ ii を Ai+1A_i + 1 回以上撫でても、幸福の過剰摂取によってあなたはがっくりしてしまいます。

ただし、別のねこを11回撫でるたびに、すべてのねこの反感度が11ずつ減少します。反感度が 00 未満になることはありません。

最初、すべてのねこの反感度は 00 です。

あなたは、ねこを撫でる順番と回数を自由に決めることができます。

このとき、がっくりすることなく、最大で何匹のねこから幸福を得ることができますか?

制約

  • 1≤N≤1051 \leq N \leq 10^5
  • 1≤Ai,Bi≤1041 \leq A_i, B_i \leq 10^4
  • 入力される値はすべて整数にゃ

入力

以下の形式で与えられます。

NN A1A_1 B1B_1 ⋮\vdots ANA_N BNB_N

出力

答えを一行で出力してください。

サンプル 1

入力

2
5 4
3 2

出力

2

サンプル 2

入力

1
3 2

出力

0

サンプル 3

入力

3
2 2
2 2
3 2

出力

3

参加受付は終了しました。