Bessie needs to produce energy as possible in her mooclear reactor. She has $$$n$$$ different particles.

Each particle is defined by two integers $$$x$$$ and $$$y$$$. The particle generates $$$x$$$ units of energy but has a reactivity $$$y$$$, meaning that it can only exist together with at most $$$y$$$ other particles in the reactor. Formally, if this particle is chosen to generate energy, then at most $$$y$$$ particles (other than itself) can also be chosen to generate energy.

Bessie must choose a subset of particles that satisfy this constraint to generate energy. The amount of energy that she generates is equal to the sum of the energies of the particles in the subset.

There is a shop with $$$m$$$ particles. Bessie can buy exactly one particle from the shop. For each particle in the shop, determine the maximum total energy that Bessie would be able to produce if she were to buy only that particle from the shop. Bessie is not required to use the particle that is purchased from the shop.

Input

The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n, m \leq 2 \cdot 10^5$$$) — the number of particles that Bessie has and the number of particles in the shop, respectively.

The $$$i$$$-th of the next $$$n$$$ lines contains two integers $$$x$$$ and $$$y$$$ ($$$1 \leq x \leq 10^9$$$, $$$0 \leq y \leq n$$$) — the energy and reactivity of Bessie's $$$i$$$-th particle.

The $$$j$$$-th of the next $$$m$$$ lines contains two integers $$$x$$$ and $$$y$$$ ($$$1 \leq x \leq 10^9$$$, $$$0 \leq y \leq n$$$) — the energy and reactivity of the shop's $$$j$$$-th particle.

It is guaranteed that the sum of $$$n$$$ over all test cases and the sum of $$$m$$$ over all test cases do not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, print $$$m$$$ integers. The $$$i$$$-th integer should be the maximum total energy that Bessie can produce if she purchases the $$$i$$$-th particle from the shop.

Note

In the first test case:

If Bessie buys particle $$$4$$$, then it is optimal for her to only use particle $$$1$$$ and generate $$$67$$$ energy units.
If she buys particle $$$5$$$, then she should only use particle $$$5$$$, which generates $$$100$$$ energy units.
If she buys particle $$$6$$$, then she should use particles $$$3$$$ and $$$6$$$, for a total of $$$69$$$ energy units.

Mooclear Reactor 2

Examples