CF436F Banners

所有现代移动应用程序都分为免费版和付费版。即使是单个应用开发者，通常也会发布两个版本：一个无广告的付费版和一个带广告的免费版。 假设付费版应用的价格为 $p$（$p$ 是整数）卢布，免费版应用包含 $c$ 个广告条。每个用户可以用两个整数描述：$a_i$ —— 该用户愿意为付费版支付的最大卢布数，$b_i$ —— 该用户在免费版中能容忍的最大广告数。 每个用户的行为完全确定： - 如果 $b_i \geq c$，则他使用免费版； - 否则，如果 $a_i \geq p$，他购买无广告的付费版； - 否则，该用户不会使用这个应用。 每个免费版用户为开发者带来 $c\times w$ 卢布的收益。每个付费版用户带来 $p$ 卢布的收益。 你的任务是帮助应用开发者选择最优的 $p$ 和 $c$。即，对于每个 $c$ 从 $0$ 到 $(\max b_i)+1$，需要确定应用能够获得的最大收益以及相应的最优价格 $p$。

第一行包含两个整数 $n$ 和 $w$（$1 \leq n \leq 10^5$；$1 \leq w \leq 10^5$），分别表示用户数和每条广告带来的收益。 接下来的 $n$ 行，每行包含两个整数 $a_i$ 与 $b_i$（$0 \leq a_i, b_i \leq 10^5$），分别表示第 $i$ 个用户的特性。

输出 $(\max b_i) + 2$ 行，第 $i$ 行输出两个整数：$pay$ —— 当 $c = i-1$ 时应用能够获得的最大收益，以及对应的最优价格 $p$（$0 \leq p \leq 10^9$）。如果有多个最优解，输出其中任意一个均可。

由 ChatGPT 5 翻译