分数: 500 点
问题陈述
高桥将参加一场饮食比赛。团队 N 成员将参加本次比赛,高桥的队伍包括 N 玩家编号 1 通过 N 从最小到最大。的 消耗系数 会员的 会员人数 i is A_i.
在比赛中, N 食品编号 将呈现 1 通过 N ,并且 难度 食品 i is F_i。比赛详情如下:
- 一个团队应为每种食物分配一名成员,并且不应为多种食物分配同一名成员。
- 需要 x \times y 会员吃完食物的秒数,其中 x 为会员的消费系数, y 是菜品的难度。
- 团队得分是单个成员吃完食物所需的最长时间。
比赛前,高桥队决定进行一些训练。在一组训练中,会员可以将自己的消费系数降低 1,只要不低于 0。然而,出于财务原因, 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 in (4-4) \times 3 = 0 秒。
- 会员 2 确实 1 一套训练和吃的食物 3 in (2-1) \times 1 = 1 第二。
- 会员 3 确实 0 套训练和吃食物 1 in (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