← 返回题目列表

AtCoder · abc144_e

E. 暴食

中文机器翻译题面 查看原题

分数: 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