AT_arc186_c [ARC186C] Ball and Box

[problemUrl]: https://atcoder.jp/contests/arc186/tasks/arc186_c 球橋さんと箱木さんはボールと箱を使ったゲームをします。 最初、球橋さんは $ M $ 種類のボールをそれぞれ $ 10^{100} $ 個ずつ持っていて、 箱木さんは $ 10^{100} $ 円持っています。 また、$ N $ 個の箱があり、$ i $ 番目の箱の容量は $ V_i $ で、値段は $ P_i $ 円です。ゲーム中、箱木さんはいつでも好きな箱を買うことができます。 このゲームでは、ゲームが終わるまで以下の操作を繰り返します。 1. 球橋さんはボールを $ 1 $ つ選び、箱木さんに渡す。 2. 箱木さんは渡されたボールを受け取るか、受け取らずにゲームを終えるかを選ぶ。 3. ボールを受け取った場合、箱木さんは購入済みの箱を $ 1 $ つ選び、受け取ったボールを入れる。 4. ボールを入れた箱が以下の条件を満たしている場合、箱木さんは $ 1 $ 円をもらう。そうでない場合、ゲームを終える。 - 箱の中のボールの個数は、その箱の容量以下である。 - 箱の中のボールの種類は、すべて同じである。 球橋さんは、ゲーム終了時の箱木さんの所持金がなるべく少なくなるための最適な行動をし、反対に、箱木さんはなるべく多くなるための最適な行動をします。 ゲームを通して、箱木さんの所持金はいくら増えますか？ ただし、両者ともにすべての情報が公開されているとします。特に、球橋さんは、それぞれの箱について、容量と値段、どの種類のボールがいくつ入っているかを見ることができます。 また、箱木さんの初期の所持金は十分多く、お金が足りなくて箱が買えなくなることはないことに注意してください。 $ 1 $ つの入力ファイルにつき、$ T $ 個のテストケースを解いてください。

入力は以下の形式で標準入力から与えられる。ここで $ \mathrm{case}_i $ は $ i $ 番目のテストケースを意味する。 > $ T $ $ \mathrm{case}_1 $ $ \mathrm{case}_2 $ $ \vdots $ $ \mathrm{case}_T $ 各テストケースは以下の形式で与えられる。 > $ N $ $ M $ $ V_1 $ $ P_1 $ $ V_2 $ $ P_2 $ $ \vdots $ $ V_N $ $ P_N $

両者が最適に行動したときの、箱木さんの最終的な所持金と最初の所持金の差を出力せよ。

### 制約 - $ 1\le\ T,N,M\le\ 3\times\ 10^5 $ - $ 1\le\ V_i,P_i\ \le\ 10^9 $ - $ T $ 個のテストケースに対する $ N $ の総和は $ 3\times\ 10^5 $ 以下 - 入力はすべて整数 ### Sample Explanation 1 最初のテストケースでは $ 2 $ 種類のボールと $ 3 $ つの箱を使います。 $ 2 $ 種類のボールをそれぞれ白のボールと黒のボールと呼び、$ i $ 種類目の箱を箱 $ i $ と呼ぶことにします。 このテストケースについて、所持金が $ 2 $ 円増えるゲームの進み方の例を示します。 1. 球橋さんが白のボールを選び、渡す。 2. 箱木さんはボールを受け取り、箱 $ 2 $ を $ 1 $ 円で買って白のボールを入れる。 - 箱 $ 2 $ には白のボールが $ 1 $ 個入っている。これは条件を満たしているため、箱木さんは $ 1 $ 円をもらう。 3. 球橋さんが白のボールを選び、渡す。 4. 箱木さんはボールを受け取り、箱 $ 2 $ に白のボールを入れる。 - 箱 $ 2 $ には白のボールが $ 2 $ 個入っている。これは条件を満たしているため、箱木さんは $ 1 $ 円をもらう。 5. 球橋さんが黒のボールを選び、渡す。 6. 箱木さんはボールを受け取り、箱 $ 3 $ を $ 1 $ 円で買って黒のボールを入れる。 - 箱 $ 3 $ には黒のボールが $ 1 $ 個入っている。これは条件を満たしているため、箱木さんは $ 1 $ 円をもらう。 7. 球橋さんが白のボールを選び、渡す。 8. 箱木さんはボールを受け取り、箱 $ 2 $ に白のボールを入れる。 - 箱 $ 2 $ には白のボールが $ 3 $ 個入っている。これは条件を満たしているため、箱木さんは $ 1 $ 円をもらう。 9. 球橋さんが白のボールを選び、渡す。 10. 箱木さんは受け取らずにゲームを終えることを選ぶ。 最終的に、箱 $ 2 $ には白のボールが $ 3 $ 個、箱 $ 3 $ には黒のボールが $ 1 $ 個入っています。 合計で $ 2 $ 円使って $ 4 $ 円もらったので、所持金は $ 2 $ 円増えました。 $ 2 $ つめのテストケースでは、球橋さんは、箱木さんにお金を稼がせないような行動ができます。