Bột Ma Thuật

Apollinaria muốn nướng bánh. Để nướng được một chiếc bánh, cô cần đúng $a_i$ gam của nguyên liệu thứ $i$ với mỗi $i=1,2,\dots ,n$.

Hiện tại cô có $b_i$ gam của nguyên liệu thứ $i$. Ngoài ra, cô có thêm $k$ gam bột ma thuật — loại bột này có thể thay thế cho bất kỳ nguyên liệu nào (mỗi gam bột ma thuật thay được đúng 1 gam của một nguyên liệu bất kỳ tuỳ chọn).

Hãy xác định số chiếc bánh nhiều nhất mà Apollinaria có thể nướng được.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên dương $n$ và $k$ — số loại nguyên liệu và số gam bột ma thuật.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$ — lượng nguyên liệu cần cho mỗi chiếc bánh.
• Dòng thứ ba chứa $n$ số nguyên $b_1,b_2,\dots ,b_n$ — lượng nguyên liệu Apollinaria đang có.

Dữ liệu ra

In ra một số nguyên duy nhất — số chiếc bánh nhiều nhất có thể nướng được.

Ràng buộc

• $1\le n\le 100000$
• $1\le k\le {10}^9$
• $1\le a_i\le {10}^9$
• $1\le b_i\le {10}^9$

Ví dụ