配点 : $650$ 点

問題文

あなたは 精進 をすることにしました。精進とは、AtCoder の問題を大量に解くことをいいます。 精進は何日か掛けて行われます。1 日における精進は次の手順で行われます。

• その日に $M$ 問の問題を解くとする。各問題には非負整数対 $(A, B)$ が 難易度 と呼ばれる値としてついている。
• まず、$M$ 問を自由な順番に並べ替える。そして、並び替えた後の順に問題を 1 問ずつ解いていく。
• あなたは 疲労度 という値を持っている。1 日のはじめの疲労度は $0$ であり、難易度が $(A, B)$ である問題を解くごとに疲労度が $x$ から $Ax + B$ に変化する。
• $M$ 問すべて解いた時点での疲労度を、その日の 消費した体力 と呼ぶ。

$N$ 問の AtCoder の問題が並んでいて、順に問題 $1$, 問題 $2$, $\dots$, 問題 $N$ と呼びます。問題 $i$ の難易度は $(A_i, B_i)$ です。 あなたは精進を行うことで $N$ 問の問題を全て解くことにしました。 精進は次の手順で行います。以下では問題 $L$, 問題 $L+1$, $...$, 問題 $R$ からなる問題の列を $[L, R]$ と呼びます。

• $1$ 以上 $N$ 以下の整数 $K$ を自由に選ぶ。精進する日数を $K$ 日とする。
• $N$ 問の問題の列を、$K$ 個の非空な連続部分列に分割して、前から $i$ 番目の列を $S_i$ とする。
  形式的に説明すると、狭義単調増加な非負整数列 $x_0, x_1, \dots, x_K$ のうち $1 = x_0$ かつ $x_K = N + 1$ を満たすものを 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$ とします。(ここで $X$ について、$\sum_{i = 1}^N B_i \leq X$ が保証されています。この制約下において条件を満たす $D$ は必ず存在します。) また、$K=D$ である精進において、精進全体での消費した体力の総和として取り得る最小の値を $M$ とします。

$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$ を空白区切りで出力せよ。

3 100
2 2
3 4
5 7

1 52

このテストケースでは $X$ に関する条件を満たしながら $1$ 日で全ての問題を解くことが可能です。 以下の手順で精進を行うことで、精進全体での消費した体力は $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$ となる。
• 問題を (問題 $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

このテストケースは、1 番目のテストケースの $X$ を $100$ から $30$ に変えたものです。よって、 $X$ に関する条件を満たしながら $1$ 日で全ての問題を解くことは不可能です。

以下の手順に従って精進を $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$ となる。
• 問題を (問題 $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$ となる。
• 問題を (問題 $3$) の順に並べる。
• はじめ、疲労度は $0$ である。
• 問題 $3$ を解く。疲労度は $5 \times 0 + 7 = 7$ に変化する。
• 全ての問題を解いた時点での疲労度は $7$ である。よって $2$ 日目の消費した体力は $7$ となる。
• 精進全体での消費した体力の総和は $10 + 7 = 17$ である。

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

5 50000000

$1$ 日 $1$ 問ずつ解いていく精進が答えとなります。

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