Gluttony

Source: AtCoder

Version: Phuoc Hung OJ Extended

Problem Statement

There are $N$ member coefficients $A_i$ and $N$ food difficulties $F_i$. Pair them bijectively; a pair $(x,y)$ takes $xy$ seconds. At most $K$ training steps may decrease coefficients by one, not below zero. Minimize the maximum paired product.

Input

The first line contains $N,K$. Then arrays $A$ and $F$.

Output

Print the minimum possible score.

Subtasks

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

Example

Input

3 5
4 2 1
2 3 1

Output

2

Explanation

An optimal training and pairing achieves maximum product 2.