← 返回题目列表

Codeforces · 436/F

F. 横幅

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

所有现代移动应用程序都分为免费和付费。即使是单个应用程序开发人员也经常发布两个版本:没有广告的付费版本和有广告的免费版本。

假设该应用程序的付费版本需要花费 p(p 是整数)个卢布,而该应用程序的免费版本包含 c 个广告横幅。每个用户可以用两个整数来描述:ai——该用户愿意为应用程序的付费版本支付的卢布数量,bi——他愿意在免费版本中容忍的横幅数量。

每个成员的行为应被视为严格确定性的:

- 如果对于用户 i,值 bi 至少为 c,那么他使用免费版本,
- 否则,如果ai值至少为p,那么他购买没有广告的付费版本,
- 否则用户根本不会使用该应用程序。

免费版本的每个用户带来c×w卢布的利润。付费版本的每个用户带来p卢布的利润。

您的任务是帮助应用程序开发人员选择最佳参数 p 和 c。也就是说,了解用户的所有特征,对于从 0 到 (max bi) + 1 的每个 c 值,您需要确定应用程序的最大利润和相应的参数 p。

输入

第一行包含两个整数 n 和 w (1 ≤ n ≤ 105; 1 ≤ w ≤ 105) — 用户数量和单个横幅的利润。接下来的 n 行中的每一行都包含两个整数 ai 和 bi (0 ≤ ai, bi ≤ 105) — 第 i 个用户的特征。

输出

打印 (max bi) + 2 行,第 i 行打印两个整数: pay — c = i - 1 时获得的最大利润,p (0 ≤ p ≤ 109) — 对应的最优应用成本。如果有多个最优解,则打印其中任意一个。

示例

输入 #1

2 1
2 0
0 2

输出 #1

0 3
3 2
4 2
2 2

输入 #2

3 1
3 1
2 2
1 3

输出 #2

0 4
3 4
7 3
7 2
4 2