← 返回题目列表

AtCoder · abc305_h

Ex. 精进

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

分数: 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