Ăn nhanh (Gluttony)

Nguồn: AtCoder

Phiên bản: Phước Hưng OJ Extended

Đề bài

Có $N$ thành viên với hệ số tiêu hóa $A_i$ và $N$ món ăn với độ khó $F_i$. Mỗi thành viên nhận đúng một món và mỗi món được giao cho đúng một người. Nếu một người có hệ số $x$ ăn món có độ khó $y$, thời gian là $xy$.

Trước cuộc thi, có thể thực hiện tổng cộng nhiều nhất $K$ lần luyện tập. Mỗi lần giảm hệ số của một thành viên đi $1$, nhưng không được giảm dưới $0$.

Sau khi chọn cách luyện tập và ghép người với món tối ưu, hãy tìm thời gian lớn nhất của một người nhỏ nhất có thể.

Input

Dòng đầu chứa $N,K$. Dòng thứ hai chứa $A_1,\ldots,A_N$. Dòng thứ ba chứa $F_1,\ldots,F_N$.

Output

In điểm số nhỏ nhất.

Subtask

• Subtask 1 — 20%: $N\le50$.
• Subtask 2 — 30%: $N\le5000$.
• Subtask 3 — 50%: $1\le N\le2\cdot10^5$, $0\le K\le10^{18}$, $1\le A_i,F_i\le10^6$.

Ví dụ

Input

3 5
4 2 1
2 3 1

Output

2

Giải thích

Ghép hệ số sau luyện tập $0,1,1$ với độ khó $3,1,2$ có thời gian lớn nhất bằng $2$, và không thể giảm thấp hơn.