SANXUAT - Sản xuất

A product is made from n parts numbered from 1 to n. When producing, the i-th part can be chosen as one of ki brands, if we choose the jth brand (j = 1..ki) it will give us a profit of tij (1 ≤ tij ≤ 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 ki indicates the number of brands, the next ki indicates the corresponding tij 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

Added by:Hoàng Phú
Date:2017-02-21
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.