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 \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 翻译