题目描述

高橋くんは AtCoder 商店を経営しています。 AtCoder 商店には $N$ 人の客が訪れ、$M$ 個の商品が売られています。 $i$ 番目 $(1\leq\ i\leq\ N)$ の客は購買意欲 $B\ _\ i$ を持っています。 $j$ 番目 $(1\leq\ j\leq\ M)$ の商品の商品価値は $C\ _\ j$ です。

高橋くんはそれぞれの商品に値段をつけます。 $i$ 番目の客は、$j$ 番目の商品の値段 $P\ _\ j$ が次の条件を満たすような商品のみを、すべて $1$ 個ずつ購入します。

• $B\ _\ i+C\ _\ j\geq\ P\ _\ j$

$j=1,2,\ldots,M$ について、高橋くんが売り上げが最大になるような値段をつけたときの $j$ 番目の商品の売り上げを求めてください。 ただし、$j$ 番目の商品の売り上げとは、$P\ _\ j$ に $j$ 番目の商品を買う人数をかけたものです。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $M$ $B\ _\ 1$ $B\ _\ 2$ $\ldots$ $B\ _\ N$ $C\ _\ 1$ $C\ _\ 2$ $\ldots$ $C\ _\ M$

输出格式

$j=1,2,\ldots,M$ について、$j$ 番目の商品の売り上げを空白区切りで $1$ 行に出力せよ。

题目大意

给定 $N$ 位顾客，$M$ 件商品，每位顾客有一个购买意向 $B_i$，每一件商品有一个价值 $C_i$。

设定每个商品的价格为 $P_i$，一个顾客 $i$ 会买一个商品 $j$ 当且仅当 $B_i + C_j \ge P_j$。

对于每一个商品，设置价格 $P_i$ 使销售额最大（销售额等于价格乘以购买人数），输出销售额。

• $1 \le N, M \le 2 \times 10^5$；
• $0 \le B_i , C_i \le 10^9$。

5 4
100 200 300 400 500
120 370 470 80

1280 2350 2850 1140

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\leq\ N\leq2\times10^5$
• $1\leq\ M\leq2\times10^5$
• $0\leq\ B\ _\ i\leq10^9\quad(1\leq\ i\leq\ N)$
• $0\leq\ C\ _\ i\leq10^9\quad(1\leq\ i\leq\ M)$
• 入力はすべて整数

Sample Explanation 1

たとえば、$1$ 番目の商品の値段を $320$ にすると、$2,3,4,5$ 番目の客が購入します。 $1$ 番目の商品の売り上げは $1280$ になります。 $1$ 番目の商品の売り上げを $1280$ より大きくすることはできないので、$1$ 番目に出力すべき値は $1280$ です。

Sample Explanation 2

購買意欲が同じ $2$ 人や、商品価値が同じ $2$ 品があることもあります。

Sample Explanation 4

売り上げが $32\operatorname{bit}$ 整数におさまらない場合があることに注意してください。