זהו היום האחרון של החופשה שלכם, והחלטתם לקנות מזכרות שיזכירו לכם את התקופה הנעימה הזאת. יש $n$ סוחרים, ואצל כל אחד מהם מצא חן בעיניכם פריט אחד. המחיר הרשום ליד הפריט של הסוחר ה־$i$ הוא $c_i$. ברשותכם סכום כסף $S$, ואתם מוכנים להוציא אותו על המזכרות. אין לכם העדפה כלשהי, ולכן אתם פשוט רוצים לקנות כמה שיותר פריטים שונים. זו הייתה משימה קלה, אבל אנחנו מדברים על חנויות לתיירים. הן משגשגות בזכות תיירים תמימים.

לסוחר ה־$i$ יש פרמטר שכנוע $p_i$, והפרמטרים שונים בין הסוחרים. ככל שכבר יש לכם יותר מזכרות, כך הסוחר בטוח יותר שאתם מוכנים להוציא כסף על זבל חסר ערך. אם סוחר רואה שכבר קניתם $k$ מזכרות, הוא מעלה את מחיר המזכרת שלו ל־$c_i+k \cdot p_i$.

מהו מספר המזכרות המרבי שתוכלו לקנות?

קלט

השורה הראשונה מכילה שני מספרים שלמים $n$ ו־$S$ ($1 \le n \le 10^5$, $0 \le S \le 10^9$), מספר הסוחרים וסכום הכסף שברשותכם.

השורה השנייה מכילה $n$ מספרים שלמים $c_1,c_2,\ldots,c_n$ ($1 \le c_i \le 10^9$), המחירים ההתחלתיים של כל המזכרות.

השורה השלישית מכילה $n$ מספרים שלמים $p_1,p_2,\ldots,p_n$ ($0 \le p_i \le 10^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