問題文

高橋君は早食い大会に出ることにしました。この大会は $N$ 人でのチーム戦であり、高橋君のチームは年齢順に $1$ から $N$ までの番号がついた $N$ 人のメンバーからなります。メンバー $i$ の 消化コスト は $A_i$ です。

大会では $1$ から $N$ までの番号がついた $N$ 個の食べ物が用意されており、食べ物 $i$ の 食べにくさ は $F_i$ です。大会のルールは以下の通りです。

• $1$ 個の食べ物につき $1$ 人のチームメンバーを割り当てる。同じメンバーを複数の食べ物に割り当てることはできない。
• あるメンバーについて、そのメンバーの消化コストが $x$、担当する食べ物の食べにくさが $y$ のとき、その食べ物の完食には $x \\times y$ 秒かかる。
• $N$ 人のメンバーそれぞれが完食にかかる時間のうち最大値が、チーム全体の成績となる。

コンテストの前に、高橋君のチームは修行をすることにしました。各メンバーは、自分の消化コストが $0$ より小さくならない限り、$1$ 回修行するごとに自分の消化コストを $1$ 減らすことができます。ただし、修行には膨大な食費がかかるため、$N$ 人合計で $K$ 回までしか修行することができません。

各メンバーの修行回数と担当する食べ物を適切に選んだとき、チーム全体の成績は最小でいくらになるでしょうか。

制約

• 入力はすべて整数
• $1 \\leq N \\leq 2 \\times 10^5$
• $0 \\leq K \\leq 10^{18}$
• $1 \\leq A_i \\leq 10^6\\ (1 \\leq i \\leq N)$
• $1 \\leq F_i \\leq 10^6\\ (1 \\leq i \\leq N)$

入力

入力は以下の形式で標準入力から与えられます。

$N$ $K$ $A_1$ $A_2$ $...$ $A_N$ $F_1$ $F_2$ $...$ $F_N$

出力

チーム全体の成績の最小値を出力してください。

入力例 1

3 5
4 2 1
2 3 1

出力例 1

2

下のようにすることで、チーム全体の成績は $2$ になります。

• メンバー $1$ に $4$ 回修行させ、食べ物 $2$ を割り当てます。完食にかかる時間は $(4-4) \\times 3 = 0$ 秒です。
• メンバー $2$ に $1$ 回修行させ、食べ物 $3$ を割り当てます。完食にかかる時間は $(2-1) \\times 1 = 1$ 秒です。
• メンバー $3$ に $0$ 回修行させ、食べ物 $1$ を割り当てます。完食にかかる時間は $(1-0) \\times 2 = 2$ 秒です。

チーム全体の成績を $2$ より小さくすることはできないので、答えは $2$ です。

入力例 2

3 8
4 2 1
2 3 1

出力例 2

0

必ずしも $K$ 回ちょうど修行する必要はありません。

入力例 3

11 14
3 1 4 1 5 9 2 6 5 3 5
8 9 7 9 3 2 3 8 4 6 2

出力例 3

12