103057: [Atcoder]ABC305 Ex - Shojin

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Score : $650$ points

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

Input

题意翻译

## 题目描述 你决定练习,练习意味着在 AtCoder 中解决大量问题。 练习需要几天时间。每天的练习分为以下步骤。 设 $M$ 是当天要解决的问题数。每个问题都有一个称为难度的值,它是一对非负整数($A$,$B$)。 首先,以任何顺序重新排列 $M$ 个问题。然后,按该顺序逐个解决问题。 您有一个称为疲劳的值。疲劳在开始一天时为 0,当解决难度为($A$,$B$)的问题时,它从 $x$ 变为 $Ax + B$。 解决所有 $M$ 个问题的疲劳在解决当天的能量消耗中。 在 AtCoder 中有一个 $N$ 个问题的序列,按顺序称为问题 1、问题 2,…,问题 $N$。问题i的难度为($A_i$,$B_i$)。 您决定通过练习解决所有 $N$ 个问题。 练习分为以下步骤。下面,让 $[L,R]$ 表示以下问题序列:问题 $L$,问题 $L + 1$,$\cdots$,问题 $R$。 自由选择 1 到 $N$(含)之间的整数 $K$。练习将持续 $K$ 天。 将 $N$ 个问题的顺序连续子序列分成 $K$ 个非空连续子序列,并让 $S_i$ 为第 $i$ 个序列。 形式上,选择一个严格递增的非负整数序列 $x_0,x_1,\cdots,x_K$,使得 $1 = x_0$ 且 $x_K = N + 1$,并让 $S_i = [xi-1,xi-1]$ 对于 $1≤i≤K$ 中的所有问题。 然后,对于 $i = 1,2,\cdots,K$,解决第 $i$ 天练习中的所有问题 $S_i$。 你决定练习,使得整个练习中消耗的总能量最多为 $X$。 让 $D$ 是 $K$ 的最小可能值,即天数,以进行这样的练习。(在此约束下,$D$ 始终存在) 还让 $M$ 是在 $K = D$ 的情况下消耗的最小总能量。 找到 $D$ 和 $M$。 ## 输入 输入格式为: $N X$ $A_1 B_1$ $A_2 B_2$ ⋮ $A_N B_N$ ## 输出 输出 $D$ 和 $M$,用空格分隔。

Output

得分:$650$分

问题描述

你决定进行练习。练习意味着在AtCoder上解决大量问题。

  • 设$M$为当天要解决的问题数量。每个问题都有一个称为难度的值,表示为非负整数对$(A, B)$。
  • 首先,以任意顺序重新排列这$M$个问题。然后,按照该顺序逐一解决这些问题。
  • 你有一个称为疲劳的值。在一天开始时的疲劳值为$0$,在解决难度为$(A, B)$的问题时,疲劳值会从$x$变为$Ax + B$。
  • 解决完所有$M$个问题后的疲劳值称为当天的能量消耗

AtCoder中有一个称为问题$1$,问题$2$,$\dots$,问题$N$的连续问题序列。问题$i$的难度为$(A_i, B_i)$。

你决定通过练习解决所有$N$个问题。

  • 在$1$到$N$(包括$N$)之间自由选择一个整数$K$。练习将持续$K$天。
  • 将$N$个问题的序列划分为$K$个非空连续子序列,并将第$i$个序列记为$S_i$。
    正式地说,选择一个严格递增的非负整数序列$x_0, x_1, \dots, x_K$,其中$1 = x_0$且$x_K = N + 1$,并且对于$1 \leq i \leq K$,$S_i = [x_{i-1}, x_i - 1]$。
  • 然后,在练习的第$i$天解决$S_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$的条件下在一天内解决所有问题。

  • 设置$K=1$,并在第一天解决$[1, 3]$。
  • 按照以下步骤进行第一天的练习,练习过程中的总能量消耗为$52$,这是最小的。
  • 设置$K=1$,并在第一天解决$[1, 3]$。
  • 按照以下步骤进行第一天的练习,练习过程中的总能量消耗为$52$,这是最小的。

样例输入 2

3 30
2 2
3 4
5 7

样例输出 2

2 17

这个测试用例是通过将$X$从$100$更改为$30$得到的。因此,在满足$X$的条件下,在一天内解决所有问题是不可能的。

按照以下步骤进行两天的练习,可以实现两天的练习总能量消耗为$17$。

  • 设置$K = 2$,并在第一天解决$[1, 2]$,在第二天解决$[3, 3]$。
  • 按照以下步骤进行第一天的练习,练习过程中的总能量消耗为$10$。
  • 按照以下步骤进行第二天的练习,练习过程中的总能量消耗为$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

加入题单

上一题 下一题 算法标签: