C - Ball and Box Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 900 点

問題文

球橋さんと箱木さんはボールと箱を使ったゲームをします。

最初、球橋さんは M 種類のボールをそれぞれ 10^{100} 個ずつ持っていて、 箱木さんは 10^{100} 円持っています。 また、N 個の箱があり、i 番目の箱の容量は V_i で、値段は P_i 円です。ゲーム中、箱木さんはいつでも好きな箱を買うことができます。

このゲームでは、ゲームが終わるまで以下の操作を繰り返します。

  1. 球橋さんはボールを 1 つ選び、箱木さんに渡す。
  2. 箱木さんは渡されたボールを受け取るか、受け取らずにゲームを終えるかを選ぶ。
  3. ボールを受け取った場合、箱木さんは購入済みの箱を 1 つ選び、受け取ったボールを入れる。
  4. ボールを入れた箱が以下の条件を満たしている場合、箱木さんは 1 円をもらう。そうでない場合、ゲームを終える。
    • 箱の中のボールの個数は、その箱の容量以下である。
    • 箱の中のボールの種類は、すべて同じである。

球橋さんは、ゲーム終了時の箱木さんの所持金がなるべく少なくなるための最適な行動をし、反対に、箱木さんはなるべく多くなるための最適な行動をします。 ゲームを通して、箱木さんの所持金はいくら増えますか？

ただし、両者ともにすべての情報が公開されているとします。特に、球橋さんは、それぞれの箱について、容量と値段、どの種類のボールがいくつ入っているかを見ることができます。 また、箱木さんの初期の所持金は十分多く、お金が足りなくて箱が買えなくなることはないことに注意してください。

1 つの入力ファイルにつき、T 個のテストケースを解いてください。

制約

  • 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 以下
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。ここで \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

3
3 2
1 1000000000
3 1
3 1
1 300000
1000000000 1
10 4
22 5
26 45
72 21
47 39
97 2
75 35
82 24
17 46
32 22
28 67

出力例 1

2
0
28

最初のテストケースでは 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 つめのテストケースでは、球橋さんは、箱木さんにお金を稼がせないような行動ができます。

Score : 900 points

Problem Statement

Mr. Ball and Mr. Box will play a game with balls and boxes.

Initially, Mr. Ball has 10^{100} balls of each of M different types, and Mr. Box has 10^{100} yen. There are N boxes, where the i-th box has capacity V_i and costs P_i yen. During the game, Mr. Box can buy any box at any time.

In this game, the following operations are repeated until the game ends:

  1. Mr. Ball chooses one ball and gives it to Mr. Box.
  2. Mr. Box either accepts the ball or ends the game without accepting it.
  3. If Mr. Box accepts the ball, he chooses one of his purchased boxes and puts the ball in it.
  4. If the box with the ball satisfies the following conditions, Mr. Box receives 1 yen. Otherwise, the game ends.
    • The number of balls in the box does not exceed its capacity.
    • All balls in the box are of the same type.

Mr. Ball will play optimally to minimize Mr. Box's final money, while Mr. Box will play optimally to maximize it. How much will Mr. Box's money increase throughout the game?

Here, both players have access to all information. In particular, Mr. Ball can see the capacity, price, and contents (type and number of balls) of each box. Also, note that Mr. Box's initial money is large enough that he will never run out of money to buy boxes.

Solve T test cases for each input file.

Constraints

  • 1\le T,N,M\le 3\times 10^5
  • 1\le V_i,P_i \le 10^9
  • The sum of N over the T test cases is at most 3\times 10^5.
  • All input values are integers.

Input

The input is given from Standard Input in the following format, where \mathrm{case}_i represents the i-th test case:

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

Each test case is given in the following format:

N M
V_1 P_1
V_2 P_2
\vdots
V_N P_N

Output

Print the difference between Mr. Box's final and initial money when both players play optimally.

Sample Input 1

3
3 2
1 1000000000
3 1
3 1
1 300000
1000000000 1
10 4
22 5
26 45
72 21
47 39
97 2
75 35
82 24
17 46
32 22
28 67

Sample Output 1

2
0
28

In the first test case, there are two types of balls and three boxes. Let us call the two types of balls white and black balls, and call the i-th box box i. Here is an example of how the game could proceed where the money increases by 2 yen.

  1. Mr. Ball chooses and gives a white ball.
  2. Mr. Box accepts the ball, buys box 2 for 1 yen, and puts the white ball in it.
    • Box 2 contains 1 white ball. This satisfies the conditions, so Mr. Box receives 1 yen.
  3. Mr. Ball chooses and gives a white ball.
  4. Mr. Box accepts the ball and puts it in box 2.
    • Box 2 contains 2 white balls. This satisfies the conditions, so Mr. Box receives 1 yen.
  5. Mr. Ball chooses and gives a black ball.
  6. Mr. Box accepts the ball, buys box 3 for 1 yen, and puts the black ball in it.
    • Box 3 contains 1 black ball. This satisfies the conditions, so Mr. Box receives 1 yen.
  7. Mr. Ball chooses and gives a white ball.
  8. Mr. Box accepts the ball and puts it in box 2.
    • Box 2 contains 3 white balls. This satisfies the conditions, so Mr. Box receives 1 yen.
  9. Mr. Ball chooses and gives a white ball.
  10. Mr. Box chooses to end the game without accepting it.

Finally, box 2 contains 3 white balls and box 3 contains 1 black ball. Mr. Box spent 2 yen and received 4 yen, so his money increased by 2 yen.

In the second test case, Mr. Ball can play in a way that prevents Mr. Box from earning any money.