题目描述

Takahashi will take part in an eating contest. Teams of $N$ members will compete in this contest, and Takahashi's team consists of $N$ players numbered $1$ through $N$ from youngest to oldest. The consumption coefficient of Member $i$ is $A_i$.

In the contest, $N$ foods numbered $1$ through $N$ will be presented, and the difficulty of Food $i$ is $F_i$. The details of the contest are as follows:

• A team should assign one member to each food, and should not assign the same member to multiple foods.
• It will take $x \times y$ seconds for a member to finish the food, where $x$ is the consumption coefficient of the member and $y$ is the difficulty of the dish.
• The score of a team is the longest time it takes for an individual member to finish the food.

Before the contest, Takahashi's team decided to do some training. In one set of training, a member can reduce his/her consumption coefficient by $1$, as long as it does not go below $0$. However, for financial reasons, the $N$ members can do at most $K$ sets of training in total.

What is the minimum possible score of the team, achieved by choosing the amounts of members' training and allocating the dishes optimally?

高桥将参加一次进食比赛。由 $N$ 名队员组成的队伍将参加比赛，高桥的队伍由 $N$ 名队员组成，从最小到最大的队员编号为 $1$ 到 $N$ 。成员 $i$ 的消费系数为 $A_i$ 。

在比赛中，将展示编号为 $1$ 至 $N$ 的 $N$ 种食物，食物 $i$ 的_难度_为 $F_i$ 。比赛详情如下：

• 每队应为每种食物指派一名成员，不得为多种食物指派同一成员。
• 一名成员完成食物需要 $x \times y$ 秒，其中 $x$ 为该成员的消耗系数， $y$ 为菜肴的难度。
• 一个团队的得分就是单个成员完成食物所需的最长时间。

比赛前，高桥团队决定进行一些训练。在一组训练中，只要不低于 $0$ ，成员就可以将自己的消耗系数降低 $1$ 。然而，出于经济原因， $N$ 名成员总共最多只能进行 $K$ 组训练。

通过选择成员的训练量和优化菜肴分配，该小组可能获得的最低分数是多少？

输入格式

输入内容按以下格式标准输入：

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

输出格式

打印该队的最低得分。

样例 #1

样例输入 #1

3 5
4 2 1
2 3 1

样例输出 #1

2

样例 #2

样例输入 #2

3 8
4 2 1
2 3 1

样例输出 #2

0

样例 #3

样例输入 #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

说明

数据规模与约定

• 输入值均为整数
• $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)$

样例 $1$ 解释

他们可以获得 $2$ 的分数，如下所示：

• 成员 $1$ 在 $(4-4) \times 3 = 0$ 秒内完成 $4$ 组训练并吃掉食物 $2$ 。
• 成员 $2$ 进行 $1$ 组训练，在 $(2-1) \times 1 = 1$ 秒内吃完食物 $3$ 。
• 成员 $3$ 在 $(1-0) \times 2 = 2$ 秒内完成 $0$ 组训练并吃掉食物 $1$ 。

他们的得分不可能低于 $2$ ，所以答案是 $2$ 。

样例 $2$ 解释

他们可以选择不进行 $K$ 组训练。