← 返回题目列表

AtCoder · abc289_g

G. 在 AtCoder 商店购物

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

高桥经营 AtCoder 商店。 N 顾客访问商店,并且 M 物品在商店出售。 的动机 i-th (1\leq i\leq N) 客户是 B _ i。 的价值 j-th (1\leq j\leq M) 项目是 C _ j.

高桥为每件商品设定了价格。 的 i第一位顾客购买了一件 j-第一项当且仅当其价格 P _ j 满足:

  • 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- 每个的第一项 j=1,2,\ldots,M,用空格分隔。


示例输入 1

5 4
100 200 300 400 500
120 370 470 80

示例输出 1

1280 2350 2850 1140

例如,他可以设定 1-st 项目 320;那么 2-nd, 3-rd, 4-th,以及 5第一个客户将购买一个。 的销售总额为 1-st 项目将是 1280。 由于他无法完成该产品的总销售 1-st 项大于 1280, 1- 要打印的st值为 1280.


示例输入 2

4 4
0 2 10 2
13 13 0 4

示例输出 2

52 52 10 18

两个客户可能有相同的动机。 此外,两个项目可能具有相同的值。


示例输入 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- 位整数类型。