#abc289g. [abc289_g]Shopping in AtCoder store

[abc289_g]Shopping in AtCoder store

给定 NN 位顾客,MM 件商品,每位顾客有一个购买意向 BiB_i,每一件商品有一个价值 CiC_i

设定每个商品的价格为 PiP_i,一个顾客 ii 会买一个商品 jj 当且仅当 Bi+CjPjB_i + C_j \ge P_j

对于每一个商品,设置价格 PiP_i 使销售额最大(销售额等于价格乘以购买人数),输出销售额。

  • 1N,M2×1051 \le N, M \le 2 \times 10^5
  • 0Bi,Ci1090 \le B_i , C_i \le 10^9