إنه آخر يوم في إجازتك، وقد قررت شراء بعض التذكارات لتذكّرك بهذه الأوقات الجميلة. يوجد $n$ تاجرًا، وقد أعجبتك سلعة واحدة عند كل منهم. السعر المكتوب بجوار سلعة التاجر رقم $i$ هو $c_i$. معك مبلغ $S$ من المال، وأنت مستعد لإنفاقه على التذكارات. ليست لديك تفضيلات معينة، لذا تريد شراء أكبر عدد ممكن من السلع المختلفة. كان الأمر ليكون سهلًا، لكننا نتحدث عن متاجر السياح، التي تزدهر باستغلال السياح السذّج.

للتاجر رقم $i$ معامل إقناع $p_i$، وتختلف هذه المعاملات بين التجار. كلما زاد عدد التذكارات التي اشتريتها، ازداد اقتناع التاجر باستعدادك لإنفاق المال على أشياء عديمة القيمة. إذا رأى التاجر أنك اشتريت بالفعل $k$ تذكارًا، فإنه يرفع سعر تذكاره إلى $c_i+k\cdot p_i$.

ما أكبر عدد من التذكارات يمكنك شراؤه؟

الإدخال

يحتوي السطر الأول على عددين صحيحين $n$ و$S$ ($1\le n\le10^5$، $0\le S\le10^9$)، وهما عدد التجار ومبلغ المال الذي معك.

يحتوي السطر الثاني على $n$ عددًا صحيحًا $c_1,c_2,\ldots,c_n$ ($1\le c_i\le10^9$)، وهي الأسعار الابتدائية لجميع التذكارات.

يحتوي السطر الثالث على $n$ عددًا صحيحًا $p_1,p_2,\ldots,p_n$ ($0\le p_i\le10^9$)، وهي معاملات الإقناع لجميع التجار. ويُضمن أنها مختلفة.

الإخراج

اطبع عددًا واحدًا، وهو عدد التذكارات التي يمكنك شراؤها.

أمثلة

الإدخال 1

2 5
1 1
10 11

الإخراج 1

1

الإدخال 2

2 22
10 1
0 10000

الإخراج 2

2

الإدخال 3

1 0
1
0

الإخراج 3

0