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 |