Ex - Shojin

AtCoder

IDabc305_h

Time3000ms

Memory256MB

Difficulty—

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$ [samples]

Samples

Input #1

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$.

Input #2

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$.

Input #3

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

Output #3

5 50000000

The optimal practice is to solve one problem per day.

Input #4

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

Output #4

2 73647

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

Output #5

4 54468135

API Response (JSON)

{
  "problem": {
    "name": "Ex - Shojin",
    "description": {
      "content": "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",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc305_h"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You have decided to **practice**. Practice means solving a large number of problems in AtCoder.  \nPractice takes place over several days. The practice for one day is carried out in the following steps...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments