Trong ngôi nhà thông minh của ~Zinno~, ~n~ con robot được kết nối với nhau theo một mạng lưới tuần tự. Mỗi robot trong danh sách được kết nối trực tiếp với robot đứng trước và robot đứng sau nó (trừ robot đầu tiên và cuối cùng).

Để thực hiện một tác vụ cụ thể, ~Zinno~ cần kích hoạt một nhóm robot hoạt động đồng thời. Do đặc thù của mạng lưới kết nối, tín hiệu điều khiển phải được truyền theo chuỗi từ một robot đầu tiên trong nhóm đến các robot kế cận. Việc kích hoạt các robot không liên tiếp sẽ phức tạp hơn, đòi hỏi gửi nhiều tín hiệu riêng lẻ, gây tốn kém năng lượng và tăng độ trễ.

Mỗi con robot yêu cầu một lượng sạc ban đầu là ~c_i~ để có thể hoạt động. Sau khi được sạc, khi hoạt động liên tục, mỗi robot tiêu thụ một lượng điện năng là ~p_i~ mỗi đơn vị thời gian. Do yêu cầu về tính đồng bộ và hiệu quả của hệ thống điều khiển tuần tự, ~Zinno~ chỉ xem xét việc sử dụng các đoạn robot liên tiếp trong danh sách cho mỗi tác vụ.

Khi sử dụng một đoạn các con robot liên tiếp từ vị trí ~u~ đến vị trí ~v~ trong danh sách, tổng chi phí năng lượng cho tác vụ đó được tính như sau:

$$ max(c_u,c_{u+1},...,c_v)+(v-u+1)\times \sum_{i=u}^{v}p_i $$

Input

Dòng đầu tiên là số nguyên dương ~n~ và ~k~ ~(1 \le n \le 10^5, 1 \le k \le 10^{15})~

Dòng thứ hai là ~n~ số nguyên dương ~c_i~ ~(1 \le c_i \le 10^5)~

Dòng thứ ba là ~n~ số nguyên dương ~p_i~ ~(1 \le p_i \le 10^5)~

Output

Một dòng duy nhất là số robot tối đa mà ~Zinno~ có thể dùng mà tổng chi phí không quá ~k~

Subtask

• Subtask 1 : ~30\%~ số điểm có ~n \le 10^3~
• Subtask 2 : ~70\%~ số điểm còn lại Không có ràng buộc gì thêm.

Sample Input

5 25
3 6 1 3 4
2 1 3 4 5

Sample Output

3