H. Treasure Island
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Sail is on Treasure Island. He foresees that $$$n$$$ events will occur on the island, and he will leave after all events have finished. Specifically, there are the following three types of events:

  1. Some gold coins appear. For each gold coin, he can either convert it into $$$k$$$ yuan, or feed it to the God of Wealth to obtain a bullet with damage $$$k$$$;
  2. Some silver coins appear. For each silver coin, he can either convert it into $$$1$$$ yuan, or feed it to the God of Wealth to obtain a bullet with damage $$$1$$$;
  3. A monster appears. Whenever a monster with $$$x$$$ HP appears, Sail must immediately attack it using some bullets, provided that the total damage of the selected bullets is greater than or equal to $$$x$$$. If this condition cannot be met, Sail will be killed by the monster. Once used, bullets are consumed and cannot be reused.

He wants to know whether he can leave the island safely, and if so, what is the maximum amount of money he can have left when leaving.

Input

The first line contains a positive integer $$$T$$$ ($$$1 \le T \le 10^4$$$), indicating the number of test cases.

For each test case, the first line contains two positive integers $$$n$$$ ($$$1 \le n \le 2 \times 10^5$$$) and $$$k$$$ ($$$1 \le k \le 10^6$$$), where $$$n$$$ is the total number of events, and $$$k$$$ is the amount of money obtained from exchanging coins or the damage value of a bullet.

The next $$$n$$$ lines each contain two positive integers $$$o$$$ ($$$o \in \{1, 2, 3\}$$$) and $$$x$$$ ($$$1 \le x \le 10^6$$$), representing an event.

  • If $$$o=1$$$ or $$$o=2$$$, $$$x$$$ represents the number of gold or silver coins that appear;
  • If $$$o=3$$$, $$$x$$$ represents the HP of the monster.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \times 10^5$$$.

Output

For each test case, if Sail cannot leave safely, output $$$-1$$$; otherwise, output the maximum amount of money that can remain.

Example
Input
5
4 3
1 2
3 5
2 3
3 3
4 3
1 2
2 2
3 5
3 1
4 3
1 2
2 2
3 5
3 3
4 3
1 2
3 5
2 2
3 3
4 3
1 2
1 3
3 4
3 9
Output
0
1
0
-1
0
Note

For the second test case, Sail does the following in order:

  1. Two gold coins appear. Sail exchanges them for two bullets with damage $$$3$$$.
  2. Two silver coins appear. Sail exchanges one of them for a bullet with damage $$$1$$$, and the other for $$$1$$$ yuan.
  3. A monster with HP $$$5$$$ appears. Sail uses two bullets with damage $$$3$$$ to kill it.
  4. A monster with HP $$$1$$$ appears. Sail uses one bullet with damage $$$1$$$ to kill it.

In the end, Sail leaves with $$$1$$$ yuan.

For the fourth test case, Sail does the following in order:

  1. Two gold coins appear. Sail exchanges them for two bullets with damage $$$3$$$.
  2. A monster with HP $$$5$$$ appears. Sail uses two bullets with damage $$$3$$$ to kill it.
  3. Two silver coins appear. Sail exchanges them for two bullets with damage $$$1$$$.
  4. A monster with HP $$$3$$$ appears. The total damage of the bullets Sail currently has is less than $$$3$$$, so he is killed.

No matter how he performs the exchanges, Sail cannot leave safely, so you should output $$$-1$$$.