题目描述

商店有 $N$ 种零食。第 $i$ 种每份价格为 $P_i$，有 $C_i$ 位同学只接受这一种零食；每买一份恰好能满足其中一人。小婷的预算为 $B$，求最多能满足多少人。

输入格式

第一行两个整数 $N,B$。接下来 $N$ 行每行两个整数 $P_i,C_i$。

输出格式

输出最多能满足的人数。

输入

4 285529524196828910
230086013749504186 784727695552586562
424630587452257991 182197049192924894
307562074783771072 334098321926213975
394291142569021167 864570897757121271

输出

1

输入

9 736363855201235721
902332826391808441 19931232156591758
219979412657519170 586766529690814580
639555743840360360 783118481507168177
396461533686233042 418029167356016549
948303390670872020 859855748637174361
84782564248688541 849728767481053063
600481606097622636 182611949298477359
552626285194837188 832493278478171686
451218106130455535 569644465381568359

输出

8

输入

19 727855867507249765
434223546576351215 238673504294715731
13179456978892151 815342688809942212
397635421235728131 961602009481419956
239306888428039216 88371244978823417
570345951014865651 245798612220351206
106972953766164633 912367591198824173
834458426833282100 583919431742791009
28312408697921554 661209799337255010
33718404900260418 604217096203466322
968049273457676340 553162748293812717
383521070777194747 4623907533182677
101613401551399944 5743851876911408
194623486472305463 496064217837313641
571698814407577401 417593719619660787
741192854089358323 228015217737354426
384718555962882731 936812145877865205
344152117489844281 358711189464892166
425811760618700497 392041709395883628
459649330879105834 152993392054585546

输出

55

数据范围

$1\le N\le10^5$，$1\le B,P_i,C_i\le10^{18}$。