题目描述

あなたは 精進 をすることにしました。精進とは、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$ を求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $X$ $A_1$ $B_1$ $A_2$ $B_2$ $\vdots$ $A_N$ $B_N$

输出格式

$D$ および $M$ を空白区切りで出力せよ。

题目大意

题目描述

你决定练习，练习意味着在 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$，用空格分隔。

3 100
2 2
3 4
5 7

1 52

3 30
2 2
3 4
5 7

2 17

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

5 50000000

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

提示

制約

• $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$
• 入力される値は全て整数

Sample Explanation 1

このテストケースでは $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$ となる。 - 精進全体での消費した体力の総和もまた $52$ である。

Sample Explanation 2

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

Sample Explanation 3

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