A product is made from n parts numbered from 1 to n. When producing, the i-th part can be chosen as one of k_i brands, if we choose the jth brand (j = 1..k_i) it will give us a profit of t_ij (1 ≤ t_ij ≤ 100)

Requirements: Choose exactly n details to produce the product so that the profit is maximum and does not exceed m.

Input

The first line gives t (t ≤ 100) which indicates the number of test cases, each test case has the following format:

• The first line records two positive integers m and n.
• Next n lines, the i-th line tells us about the i-th detail: the first number k_i indicates the number of brands, the next k_i indicates the corresponding t_ij profit.

Output

Including t rows, each row records a number that is the corresponding largest profit found, if not found, write the result -1.

Example

Input:
1
20 3
3 6 4 8
2 5 10
4 1 5 3 5

Output:
19