Ex - Shojin
当前没有测试数据。
Ex - Shojin
得分：650 分
问题描述
你决定进行练习。练习意味着在 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$）。
此外，令 $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$
- 所有输入都是整数。
输入
从标准输入读入数据，数据格式如下：
输出
按照顺序输出 $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