分数: 650 点
问题陈述
您已决定 练习。实践意味着在 AtCoder 中解决大量问题。
练习需要几天时间。一天的练习是按以下步骤进行的。
- 让 M 是当天要解决的问题数。每个问题都有一个值,称为 难度,这是一对非负整数 (A, B).
- 首先,重新排列 M 问题不限顺序。然后,按照顺序一一解决问题。
- 你有一个名为 疲劳。一天开始时的疲劳感是 0,它从 x to Ax + B 遇到困难时 (A, B).
- 解决完所有问题后的疲劳 M 问题被称为 消耗的能量 那天。
有一个序列 N AtCoder 中的问题,称为问题 1,问题 2, \dots,问题 N 按顺序。问题的难度 i is (A_i, B_i).
你决定解决所有问题 N 通过练习解决问题。
练习按以下步骤进行。下面,让 [L, R] 表示以下问题序列:问题 L,问题 L+1, ...,问题 R.
- 选择一个整数 K 之间自由 1 和 N,包括在内。练习将持续下去 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,解决所有问题 S_i 上 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 to 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