AtCoder 商店购物

题目描述

高桥君经营着 AtCoder 商店。 有 $N$ 位顾客光顾这家商店,店内售卖 $M$ 件商品。 第 $i$ 位顾客 $(1 \le i \le N)$ 的购买欲为 $B_i$。 第 $j$ 件商品 $(1 \le j \le M)$ 的价值为 $C_j$。

高桥君为每件商品设定价格。 第 $i$ 位顾客会购买第 $j$ 件商品,当且仅当该商品的价格 $P_j$ 满足:

$B_i + C_j \ge P_j$。

对每个 $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$

输出格式

对于每个 $j = 1, 2, \ldots, M$,在一行中输出第 $j$ 件商品的销售额,以空格分隔。

样例

5 4
100 200 300 400 500
120 370 470 80

1280 2350 2850 1140

例如,他可以把第 1 件商品的价格定为 $320$,此时第 2、3、4、5 位顾客都会购买一件。 第 1 件商品的销售额为 $1280$。 由于无法让第 1 件商品的销售额超过 $1280$,因此要输出的第 1 个值是 $1280$。

4 4
0 2 10 2
13 13 0 4

52 52 10 18

可能有两位顾客的购买欲相同,也可能有两件商品的价值相同。

12 15
16 592 222 983 729 338 747 61 451 815 838 281
406 319 305 519 317 590 507 946 365 5 673 478 340 176 2

6280 5466 5382 7410 5454 8120 7290 11680 5870 3670 8950 7000 5620 4608 3655

5 5
1000000000 1000000000 1000000000 1000000000 1000000000
1000000000 1000000000 1000000000 1000000000 1000000000

10000000000 10000000000 10000000000 10000000000 10000000000

数据范围

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

提示

注意销售额可能无法用 32 位整数类型表示。