AT_abc305_h [ABC305Ex] Shojin

[problemUrl]: https://atcoder.jp/contests/abc305/tasks/abc305_h あなたは **精進** をすることにしました。精進とは、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 $ を空白区切りで出力せよ。

### 制約 - $ 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 $ 問ずつ解いていく精進が答えとなります。