Rarity is collecting special crystals for the upcoming Equestria games. Currently, she is in a gem cave and has found a bunch of crystals.

To Rarity's discerning eye, crystals have three properties: a color, a reactivity level, and a fashion value. Of course, Rarity wants to collect crystals to maximize the total fashion value.

Rarity knew she wouldn't have enough room in just one bag for all the crystals, so she brought two.

Well, it turns out that space isn't the main issue that Rarity has. These special crystals are reactive. In their current environment, they are relatively stable, but once Rarity has put them in her bag and taken them out of the gem cave, if the reactivity levels are too high, the gems will disintegrate, and thus lose all their fashion value.

There are two ways that reactions can happen:

1. If there are too many gems of the same color, in the same bag, they'll disintegrate.
2. If the total reactivity level of the crystals in the same bag is too high, they'll disintegrate.

Different colors of gems have different reaction limits. Also, it is possible that some colors of gems are simply unstable and will always disintegrate when taken outside the cave.

Twilight Sparkle had studied these crystals at some point, and discovered a way to stop crystals from reacting. The material is difficult to create, but she has still given Rarity a separate, special bag which can hold only a single crystal, but that crystal won't react no matter what while it is in the bag.

This is the situation Rarity is in, and she needs your help.

Input

You will be given T, the number of test cases to follow.

Each test case begins with a single line containing the values R and C:
R is the maximum reactivity level allowed in a regular bag without having the crystals disintegrate.
C is the number of different colors of gems that Rarity currently can see.

The next C lines will be of the form L N r₁ v₁ r₂ v₂ ... r_N v_N.
L is the limit for how many crystals of this color can be in the same bag without reacting.
N is the number of crystals of this color that Rarity can see.
The next 2×N numbers are pairs indicating the reactivity level and the fashion value of each of the N gems.

Test cases will follow immediately after each other (see sample input)

Limits:
1 ≤ R ≤ 100
1 ≤ C ≤ 10
0 ≤ L ≤ 3
1 ≤ N ≤ 10

For any reactivity level 'r' or fashion value 'v', 1 ≤ r, v ≤ 1000

Note that Rarity's two regular bags are large enough to hold any number of crystals.

Output

For each test case, on a separate line, output the maximum fashion value of the crystals that Rarity is able to collect in her bags.

Example

Input:
2
10 2
1 2 5 1 5 1
2 2 6 1 6 1
5 3
3 3 1 1 1 1 1 1
3 3 1 1 1 1 1 1
3 3 1 1 1 1 1 1

Output:
3
9

Final note: The time limit for each test case is at a minimum, 3× my Java solution. There are a few files with the input being 1-2MB.