AT_abc289_g.[ABC289G] Shopping in AtCoder store

高桥君经营着 AtCoder 商店。AtCoder 商店有 $N$ 位顾客光临，售卖 $M$ 种商品。第 $i$ 位顾客（$1\leq i\leq N$）有一个购买意愿 $B_i$。第 $j$ 种商品（$1\leq j\leq M$）的商品价值为 $C_j$。

高桥君需要为每个商品定价。第 $i$ 位顾客只会购买第 $j$ 种商品，当且仅当该商品的价格 $P_j$ 满足以下条件：

• $B_i + C_j \geq P_j$

每个顾客对每种商品最多只会购买 $1$ 件。

请你对于 $j=1,2,\ldots,M$，求出当高桥君为第 $j$ 种商品定价，使得其销售额最大时，该商品的最大销售额。这里，第 $j$ 种商品的销售额定义为 $P_j$ 乘以购买该商品的顾客人数。

输入按以下格式从标准输入读入。

$N$ $M$
$B_1$ $B_2$ $\ldots$ $B_N$
$C_1$ $C_2$ $\ldots$ $C_M$

请输出 $M$ 个整数，第 $j$ 个数表示第 $j$ 种商品的最大销售额。各数之间用空格隔开，输出一行。

限制条件

• $1\leq N\leq 2\times 10^5$
• $1\leq M\leq 2\times 10^5$
• $0\leq B_i\leq 10^9\quad(1\leq i\leq N)$
• $0\leq C_j\leq 10^9\quad(1\leq j\leq M)$
• 所有输入均为整数

样例解释 1

例如，将第 $1$ 种商品的价格定为 $320$ 时，第 $2,3,4,5$ 位顾客会购买。此时第 $1$ 种商品的销售额为 $1280$。无法使第 $1$ 种商品的销售额超过 $1280$，因此输出的第 $1$ 个值应为 $1280$。

样例解释 2

也可能存在有 $2$ 位顾客购买意愿相同，或有 $2$ 种商品商品价值相同的情况。

样例解释 4

请注意，销售额可能会超过 $32$ 位整数的范围。

由 ChatGPT 4.1 翻译