AT_abc305_h [ABC305Ex] Shojin

题目描述

你决定进行“精进”。“精进”指的是大量解答 AtCoder 的题目。
精进需要花费若干天。一天的精进按照以下步骤进行：

• 假设这一天你要解 $M$ 道题。每道题都带有一个非负整数对 $(A, B)$，称为难度。
• 首先，可以任意排列这 $M$ 道题的顺序。然后，按照排列后的顺序依次解题。
• 你有一个疲劳度的数值。一天开始时疲劳度为 $0$，每当解答一题难度为 $(A, B)$ 的题目时，疲劳度从 $x$ 变为 $Ax + B$。
• 解完这 $M$ 道题时的疲劳度，称为这一天消耗的体力。

有 $N$ 道 AtCoder 的题目，依次编号为第 $1$ 题、第 $2$ 题、$\dots$、第 $N$ 题。第 $i$ 题的难度为 $(A_i, B_i)$。
你打算通过精进将这 $N$ 道题全部解完。
精进的具体流程如下。以下将第 $L$ 题到第 $R$ 题的题目序列记作 $[L, R]$。

• 可以自由选择一个 $1 \leq K \leq N$ 的整数，表示精进的天数为 $K$ 天。
• 将 $N$ 道题的序列划分为 $K$ 个非空连续子序列，记第 $i$ 个子序列为 $S_i$。
  形式化地说，选择一个严格单调递增的非负整数序列 $x_0, x_1, \dots, x_K$，满足 $x_0 = 1$ 且 $x_K = N+1$，对于 $1 \leq i \leq K$，有 $S_i = [x_{i-1}, x_i - 1]$。
• 然后，对于 $i=1,2,\dots,K$，第 $i$ 天精进时解答 $S_i$ 中的所有题目。

你希望通过精进，使得精进过程中消耗的体力总和不超过 $X$。
在满足上述条件的情况下，精进天数 $K$ 能取到的最小值记为 $D$。（这里保证 $\sum_{i=1}^N B_i \leq X$，在此约束下，必然存在满足条件的 $D$。） 此外，在 $K = D$ 的精进方案中，精进过程中消耗的体力总和能取得的最小值记为 $M$。

请你求出 $D$ 和 $M$。

输入格式

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

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

输出格式

请输出 $D$ 和 $M$，以空格分隔。

输入输出样例 #1

输入 #1

3 100
2 2
3 4
5 7

输出 #1

1 52

输入输出样例 #2

输入 #2

3 30
2 2
3 4
5 7

输出 #2

2 17

输入输出样例 #3

输入 #3

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

输出 #3

5 50000000

输入输出样例 #4

输入 #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

输入 #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

说明/提示

限制条件

• $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$
• 输入的所有值均为整数

样例解释 1

在本测试用例中，可以在满足 $X$ 的条件下一天内解完所有题。按照以下步骤精进，精进过程中消耗的体力总和为 $52$，且这是最小值。

• 取 $K=1$，第 $1$ 天解 $[1, 3]$。
• 第 $1$ 天精进的具体过程如下：
  • 将题目按（第 $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

本测试用例是第一个样例中 $X$ 从 $100$ 改为 $30$ 的情况。因此，无法在满足 $X$ 的条件下一天内解完所有题。按照以下步骤精进 $2$ 天，可以达到 $M=17$。

• 取 $K=2$，第 $1$ 天解 $[1, 2]$，第 $2$ 天解 $[3, 3]$。
• 第 $1$ 天精进的具体过程如下：
  • 将题目按（第 $1$ 题、第 $2$ 题）的顺序排列。
  • 初始疲劳度为 $0$。
  • 解第 $1$ 题，疲劳度变为 $2 \times 0 + 2 = 2$。
  • 解第 $2$ 题，疲劳度变为 $3 \times 2 + 4 = 10$。
  • 解完所有题时的疲劳度为 $10$，即第 $1$ 天消耗的体力为 $10$。
• 第 $2$ 天精进的具体过程如下：
  • 将题目按（第 $3$ 题）的顺序排列。
  • 初始疲劳度为 $0$。
  • 解第 $3$ 题，疲劳度变为 $5 \times 0 + 7 = 7$。
  • 解完所有题时的疲劳度为 $7$，即第 $2$ 天消耗的体力为 $7$。
• 精进过程中消耗的体力总和为 $10 + 7 = 17$。

样例解释 3

每天只解一道题的精进方式就是答案。

由 ChatGPT 4.1 翻译