修行

题目描述

你决定进行修行。修行指的是在 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 \le i \le K$)。

然后,对于 $i=1, 2, \dots, K$,在第 $i$ 天的修行中解决 $S_i$ 中的所有题目。

你决定进行修行,使得整个修行中消耗的总能量至多为 $X$。

设 $D$ 为满足条件的修行中,天数 $K$ 的最小可能值。(这里,保证 $\sum_{i = 1}^N B_i \le X$。在该约束下,这样的 $D$ 总是存在。)

另外,设 $M$ 为满足 $K=D$ 的修行中,消耗的总能量的最小可能值。

求 $D$ 和 $M$。

输入格式

输入按以下格式从标准输入给出:

N X
A_1 B_1
A_2 B_2
⋮
A_N B_N

输出格式

用空格分隔输出 $D$ 和 $M$。

样例

3 100
2 2
3 4
5 7

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$。

3 30
2 2
3 4
5 7

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$。

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

5 50000000

最优的修行方式是每天解决一道题。

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

2 73647

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

4 54468135

数据范围

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