问题描述

你决定练习。练习意味着在AtCoder上解决大量的问题。 练习需要几天时间。每天的练习分为以下步骤。

• 让 $M$ 成为当天要解决的问题数。每个问题都有一个名为难度的值，它是一对非负整数$(A, B)$。
• 首先，以任意顺序重新排列这 $M$ 个问题。然后按照这个顺序逐个解决问题。
• 你拥有一个名为疲劳值的值。一天开始时的疲劳值为 $0$，当解决一个难度为 $(A, B)$ 的问题时，疲劳值从 $x$ 变为 $Ax + B$。
• 解决完所有 $M$ 个问题后，疲劳值称为当天消耗的能量。

在AtCoder中有一个由 $N$ 个问题组成的序列，称为问题 $1$，问题 $2$，$\\dots$，问题 $N$，按顺序排列。问题 $i$ 的难度是 $(A_i, B_i)$。 你决定通过练习解决所有 $N$ 个问题。 练习按以下步骤进行。下面，让 \[L, R\] 表示以下问题序列：问题 $L$，问题 $L+1$，$...$，问题 $R$。

• 在 $1$ 到 $N$ 之间任意选择一个整数 $K$。练习将持续 $K$ 天。
• 将 $N$ 个问题的序列划分为 $K$ 个非空连续子序列，并让 $S_i$ 表示第 $i$ 个序列。 具体来说，选择一个严格递增的非负整数序列 $x_0, x_1, \\dots, x_K$，满足 $1 = x_0$ 和 $x_K = N + 1$，并让 S_i = \[x_{i-1}, x_i - 1\]，其中 $1 \\leq i \\leq K$。
• 然后，对于 $i=1, 2, \\dots, K$，在练习的第 $i$ 天解决 $S_i$ 中的所有问题。

你决定练习，使得在整个练习过程中消耗的总能量不超过 $X$。 设 $D$ 是这样一个练习的最小可能天数 $K$ 的值。（在这里，保证 $\\sum_{i = 1}^N B_i \\leq X$。在此约束条件下，这样的 $D$ 总是存在的。） 还设 $M$ 是这样一个练习的最小可能总能量，使得 $K=D$。

找出 $D$ 和 $M$。

约束条件

• $1 \\leq N \\leq 2 \\times 10^5$
• $1 \\leq X \\leq 10^8$
• $1 \\leq A_i \\leq 10^5$
• $1 \\leq B_i$
• $\\sum_{i=1}^N B_i \\leq X$
• 所有输入值都是整数。

---

输入

输入从标准输入给出，格式如下：

$N$ $X$ $A_1$ $B_1$ $A_2$ $B_2$ $\\vdots$ $A_N$ $B_N$

输出

以空格分隔打印 $D$ 和 $M$。

---

示例输入 1

3 100
2 2
3 4
5 7

示例输出 1

1 52

在这个测试案例中，你可以在一天内解决所有问题，同时满足 $X$ 的条件。 按照以下步骤进行，练习期间消耗的总能量将为52，这是最小值。

• 设置 $K=1$，并在第一天解决 \[1, 3\]。
• 在第一天的练习中按照以下步骤进行。
  • 按顺序排列问题（问题 $3$，问题 $2$，问题 $1$）。
  • 最初，疲劳值为 $0$。
  • 解决问题 $3$。疲劳值变为 $5 \\times 0 + 7 = 7$。
  • 解决问题 $2$。疲劳值变为 $3 \\times 7 + 4 = 25$。
  • 解决问题 $1$。疲劳值变为 $2 \\times 25 + 2 = 52$。
  • 解决完所有问题时，疲劳值为 $52$。因此，当天消耗的能量为 $52$。
• 整个练习期间消耗的总能量也为 $52$。

---

示例输入 2

3 30
2 2
3 4
5 7

示例输出 2

2 17

这个测试案例是在第一个测试案例的基础上将 $X$ 从 $100$ 变成 $30$。因此，无法在一天内解决所有问题，同时满足 $X$ 的条件。

按照以下步骤，你可以通过连续两天的练习实现 $M=17$。

• 设置 $K = 2$，并在第一天解决 \[1, 2\]，第二天解决 \[3, 3\]。
• 在第一天的练习中按照以下步骤进行。
  • 按顺序排列问题（问题 $1$，问题 $2$）。
  • 最初，疲劳值为 $0$。
  • 解决问题 $1$。疲劳值变为 $2 \\times 0 + 2 = 2$。
  • 解决问题 $2$。疲劳值变为 $3 \\times 2 + 4 = 10$。
  • 解决完所有问题时，疲劳值为 $10$。因此，第一天消耗的能量为 $10$。
• 在第二天的练习中按照以下步骤进行。
  • 按顺序排列问题（问题 $3$）。
  • 最初，疲劳值为 $0$。
  • 解决问题 $3$。疲劳值变为 $5 \\times 0 + 7 = 7$。
  • 解决完所有问题时，疲劳值为 $7$。因此，第二天消耗的能量为 $7$。
• 整个练习期间消耗的总能量为 $10 + 7 = 17$。

---

示例输入 3

5 50000000
100000 10000000
100000 10000000
100000 10000000
100000 10000000
100000 10000000

示例输出 3

5 50000000

最优练习是每天解决一个问题。

---

示例输入 4

10 100000000
5 88
66 4
52 1
3 1
12 1
53 25
11 12
12 2
1 20
47 10

示例输出 4

2 73647

---

示例输入 5

15 100000000
2387 3178
2369 5772
1 29
36 3
52 2981
196 1
36 704
3 3
1501 5185
23 628
3623 810
80 101
6579 15
681 7
183 125

示例输出 5

4 54468135