Score : $650$ points

问题描述

你决定进行 练习。练习意味着在 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$、$\dots$、问题 $R$ 这一连续问题序列。

• 自由选择一个介于 $1$ 到 $N$（包括两端点）之间的整数 $K$。练习将持续 $K$ 天。
• 将包含 $N$ 个问题的序列划分为 $K$ 个非空连续子序列，并令第 $i$ 个子序列记作 $S_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$ 天，对于 $i=1, 2, \dots, K$，解决子序列 $S_i$ 中的所有问题。

你决定进行练习以确保整个练习期间消耗的总能量不超过 $X$。
设 $D$ 为满足此条件的练习所需天数 $K$ 的最小可能值。（这里保证 $\sum_{i = 1}^N B_i \leq X$。在此约束下，这样的 $D$ 总是存在的。）
同时，设 $M$ 为满足 $K=D$ 时整个练习期间消耗的最小可能总能量。

求解 $D$ 和 $M$。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

You have decided to practice. Practice means solving a large number of problems in AtCoder.
Practice takes place over several days. The practice for one day is carried out in the following steps.

• Let $M$ be the number of problems to be solved on that day. Each problem has a value called difficulty, which is a pair of non-negative integers $(A, B)$.
• First, rearrange the $M$ problems in any order. Then, solve the problems one by one in that order.
• You have a value called fatigue. The fatigue at the beginning of the day is $0$, and it changes from $x$ to $Ax + B$ when solving a problem with difficulty $(A, B)$.
• The fatigue at the end of solving all $M$ problems is called the energy consumed for that day.

There is a sequence of $N$ problems in AtCoder, called problem $1$, problem $2$, $\dots$, problem $N$ in order. The difficulty of problem $i$ is $(A_i, B_i)$.
You have decided to solve all $N$ problems through practice.
Practice is carried out in the following steps. Below, let $[L, R]$ denote the following sequence of problems: problem $L$, problem $L+1$, $...$, problem $R$.

• Choose an integer $K$ freely between $1$ and $N$, inclusive. The practice will last $K$ days.
• Divide the sequence of $N$ problems into $K$ non-empty continuous subsequences, and let $S_i$ be the $i$-th sequence.
  Formally, choose a strictly increasing non-negative integer sequence $x_0, x_1, \dots, x_K$ such that $1 = x_0$ and $x_K = N + 1$, and let $S_i = [x_{i-1}, x_i - 1]$ for $1 \leq i \leq K$.
• Then, for $i=1, 2, \dots, K$, solve all problems in $S_i$ on the $i$-th day of practice.

You have decided to practice so that the total energy consumed throughout the practice is at most $X$.
Let $D$ be the minimum possible value of $K$, the number of days, for such a practice. (Here, it is guaranteed that $\sum_{i = 1}^N B_i \leq X$. Under this constraint, such $D$ always exists.)
Also, let $M$ be the minimum possible total energy consumed throughout a practice such that $K=D$.

Find $D$ and $M$.

Constraints

• $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$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$ $X$

$A_1$ $B_1$

$A_2$ $B_2$

$\vdots$

$A_N$ $B_N$

Output

Print $D$ and $M$ separated by a space.

Sample Input 1

3 100
2 2
3 4
5 7

Sample Output 1

1 52

In this test case, you can solve all problems in one day while satisfying the condition for $X$.
By following the steps below, the total energy consumed during the practice will be $52$, which is the minimum.

• Set $K=1$ and solve $[1, 3]$ on the first day.
• Carry out the practice on the first day in the following steps.
  • Arrange the problems in the order (problem $3$, problem $2$, problem $1$).
  • Initially, the fatigue is $0$.
  • Solve problem $3$. The fatigue changes to $5 \times 0 + 7 = 7$.
  • Solve problem $2$. The fatigue changes to $3 \times 7 + 4 = 25$.
  • Solve problem $1$. The fatigue changes to $2 \times 25 + 2 = 52$.
  • The fatigue at the end of solving all problems is $52$. Therefore, the energy consumed on this day is $52$.
• The total energy consumed throughout the practice is also $52$.

Sample Input 2

3 30
2 2
3 4
5 7

Sample Output 2

2 17

This test case is obtained by changing $X$ from $100$ to $30$ in the first test case. Therefore, it is impossible to solve all problems in one day while satisfying the condition for $X$.

By following the steps below, you can achieve $M=17$ by practicing for two days.

• Set $K = 2$, and solve $[1, 2]$ on the first day and $[3, 3]$ on the second day.
• Carry out the practice on the first day in the following steps.
  • Arrange the problems in the order (problem $1$, problem $2$).
  • Initially, the fatigue is $0$.
  • Solve problem $1$. The fatigue changes to $2 \times 0 + 2 = 2$.
  • Solve problem $2$. The fatigue changes to $3 \times 2 + 4 = 10$.
  • The fatigue at the end of solving all problems is $10$. Therefore, the energy consumed on the first day is $10$.
• Carry out the practice on the second day in the following steps.
  • Arrange the problems in the order (problem $3$).
  • Initially, the fatigue is $0$.
  • Solve problem $3$. The fatigue changes to $5 \times 0 + 7 = 7$.
  • The fatigue at the end of solving all problems is $7$. Therefore, the energy consumed on the second day is $7$.
• The total energy consumed throughout the practice is $10 + 7 = 17$.

Sample Input 3

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

Sample Output 3

5 50000000

The optimal practice is to solve one problem per day.

Sample Input 4

10 100000000
5 88
66 4
52 1
3 1
12 1
53 25
11 12
12 2
1 20
47 10

Sample Output 4

2 73647

Sample Input 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

Sample Output 5

4 54468135

update @ 2024/3/10 08:37:51