G - Shopping in AtCoder store Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

高橋くんは 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 番目の商品を買う人数をかけたものです。

制約

  • 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)
  • 入力はすべて整数

入力

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

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

出力

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

入力例 1

5 4
100 200 300 400 500
120 370 470 80

出力例 1

1280 2350 2850 1140

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

入力例 2

4 4
0 2 10 2
13 13 0 4

出力例 2

52 52 10 18

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

入力例 3

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

出力例 3

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

入力例 4

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

出力例 4

10000000000 10000000000 10000000000 10000000000 10000000000

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

Score : 600 points

Problem Statement

Takahashi runs AtCoder store. N customers visit the store, and M items are sold in the store. The motivation of the i-th (1\leq i\leq N) customer is B _ i. The value of the j-th (1\leq j\leq M) item is C _ j.

Takahashi sets a price for each item. The i-th customer buys one j-th item if and only if its price P _ j satisfies:

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

For each j=1,2,\ldots,M, find the gross sale of the j-th item when Takahashi sets the price so that the sale is maximized. The gross sale of the j-th item is defined as the product of P _ j and the number of customers that buys the j-th item.

Constraints

  • 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)
  • All values in the input are integers.

Input

The input is given from Standard Input in the following format:

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

Output

Print a line containing the gross sale of the j-th item for each j=1,2,\ldots,M, separated by spaces.

Sample Input 1

5 4
100 200 300 400 500
120 370 470 80

Sample Output 1

1280 2350 2850 1140

For example, he may set the price of the 1-st item to 320; then the 2-nd, 3-rd, 4-th, and 5-th customers will buy one. The gross sale of the 1-st item will be 1280. Since he cannot make the gross sale of the 1-st item greater than 1280, the 1-st value to be printed is 1280.

Sample Input 2

4 4
0 2 10 2
13 13 0 4

Sample Output 2

52 52 10 18

Two customers may have the same motivation. Also, two items may have the same value.

Sample Input 3

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

Sample Output 3

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

Sample Input 4

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

Sample Output 4

10000000000 10000000000 10000000000 10000000000 10000000000

Note that the gross sales may not fit into a 32-bit integer type.