这是你假期的最后一天，你决定买一些纪念品来纪念这段美好的时光。这里有 $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, \dots, c_n$ ($1 \le c_i \le 10^9$)，表示所有纪念品的初始价格。

第三行包含 $n$ 个整数 $p_1, p_2, \dots, 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