Đây là ngày cuối cùng trong kỳ nghỉ của bạn và bạn quyết định mua một vài món đồ lưu niệm để ghi nhớ khoảng thời gian tuyệt vời này. Có $n$ người bán hàng, và bạn thích một món đồ từ mỗi người trong số họ. Giá ghi bên cạnh món đồ của người bán hàng thứ $i$ là $c_i$. Bạn có $S$ tiền và sẵn sàng chi tiêu cho các món đồ lưu niệm này. Bạn không có ưu tiên cụ thể nào nên chỉ muốn mua càng nhiều món đồ khác nhau càng tốt. Công việc này lẽ ra rất dễ dàng, nhưng chúng ta đang nói về các cửa hàng du lịch, nơi họ kiếm lời từ những du khách nhẹ dạ.

Người bán hàng thứ $i$ có tham số thuyết phục $p_i$ và các tham số này là khác nhau đối với mỗi người bán hàng. Bạn càng có nhiều món đồ lưu niệm, người bán hàng càng tin chắc vào sự sẵn lòng chi tiền của bạn cho những món đồ vô giá trị. Nếu một người bán hàng thấy rằng bạn đã mua $k$ món đồ lưu niệm, họ sẽ tăng giá món đồ của mình lên thành $c_i + k \cdot p_i$.

Hỏi số lượng món đồ lưu niệm tối đa bạn có thể mua là bao nhiêu?

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên $n$ và $S$ ($1 \le n \le 10^5$, $0 \le S \le 10^9$) — số lượng người bán hàng và số tiền bạn có.

Dòng thứ hai chứa $n$ số nguyên $c_1, c_2, \dots, c_n$ ($1 \le c_i \le 10^9$) — giá ban đầu của tất cả các món đồ lưu niệm.

Dòng thứ ba chứa $n$ số nguyên $p_1, p_2, \dots, p_n$ ($0 \le p_i \le 10^9$) — tham số thuyết phục của tất cả người bán hàng. Đảm bảo rằng các tham số này là phân biệt.

Dữ liệu ra

In ra một số duy nhất — số lượng món đồ lưu niệm tối đa bạn có thể mua.

Ví dụ

Dữ liệu vào 1

2 5
1 1
10 11

Dữ liệu ra 1

1

Dữ liệu vào 2

2 22
10 1
0 10000

Dữ liệu ra 2

2

Dữ liệu vào 3

1 0
1
0

Dữ liệu ra 3

0