Gluttony

题目描述

Takahashi 将参加一场吃东西比赛。由 $N$ 名成员组成的队伍将参加这场比赛，Takahashi 的队由从年纪最小到最大的编号为 $1$ 到 $N$ 的 $N$ 名选手组成。成员 $i$ 的吃东西系数是 $A_i$。 比赛中，会有编号为 $1$ 到 $N$ 的 $N$ 道食物，食物 $i$ 的难度是 $F_i$。比赛的细节如下：

一个队伍应当给每道食物分配一名成员，并且不得将同一名成员分配给多道食物。 一个成员吃完一道食物需要 $x \times y$ 秒，其中 $x$ 是该成员的吃东西系数，$y$ 是该道菜的难度。 一个队伍的分数是单个成员吃完食物所需时间的最长值。

在比赛前，Takahashi 的队决定做一些训练。在一次训练中，一名成员可以将他/她的吃东西系数减少 $1$，只要该系数不低于 $0$。但是，出于财务原因，$N$ 名成员总共最多可以做 $K$ 次训练。 通过选择各成员的训练次数并且最优地分配菜肴，队伍能够达到的最小可能分数是多少？

输入格式

输入由标准输入给出，格式如下： $N$ $K$ $A_1$ $A_2$ $...$ $A_N$ $F_1$ $F_2$ $...$ $F_N$

输出格式

输出队伍能够达到的最小可能分数。

3 5
4 2 1
2 3 1

2

3 8
4 2 1
2 3 1

0

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

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)$他们可以通过如下方式达到分数 $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$。
他们可以选择不恰好做 $K$ 次训练。

标签: AtCoder|abc144E

来源

AtCoder|abc144E