AT_abc144_e [ABC144E] Gluttony

[problemUrl]: https://atcoder.jp/contests/abc144/tasks/abc144_e 高橋君は早食い大会に出ることにしました。この大会は $ 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 $ 回までしか修行することができません。 各メンバーの修行回数と担当する食べ物を適切に選んだとき、チーム全体の成績は最小でいくらになるでしょうか。

入力は以下の形式で標準入力から与えられます。 > $ N $ $ K $ $ A_1 $ $ A_2 $ $ ... $ $ A_N $ $ F_1 $ $ F_2 $ $ ... $ $ F_N $

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

### 制約 - 入力はすべて整数 - $ 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) $ ### Sample Explanation 1 下のようにすることで、チーム全体の成績は $ 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 $ です。 ### Sample Explanation 2 必ずしも $ K $ 回ちょうど修行する必要はありません。