Problem Description
Karl the Invoker is tired of people making fun of him for only knowing ten spells, so he has started to learn new spells to expand his repertoire. Of course, memorising incantations is a rather tedious and boring task, so Karl amuses himself in his spare time by watching television. Naturally Karl cannot watch shows in the day since he is busy training, so he records all the shows in a day to be watched later. However, because of his busy, irregular timetable, Karl doesn't have time to watch all the shows he wants. Thus, he has asked you to help him schedule his television watching for his maximum satisfaction.
Each day, Karl records at least zero television programs. Each television program lasts L time units and provides S satisfaction to Karl when watched. Karl has a varying amount of T time units each day to watch television. He can watch any number of shows recorded on or before the current day as long as the total L of the shows he watches does not exceed T.
Given the maximum time allowances of T time units for each day, as well as the daily list of shows each lasting L time units and providing S satisfaction, over N days, determine the maximum satisfaction that Karl can derive from his television watching in one day.
Input
The first line of input will consist of 1 integer, N
The rest of the intput is divided into N sections presented like so:
The first line of the ith section will consist of 2 integers, Ti and Mi
Subsequent M lines will consist of 2 integers each, representing the L and S for each show on the ith day.
Output
Output a single integer indicating the maximum satisfaction possible in one day within the given time period.
Limits
Subtask 1 (9%): N = 1; all L = 1; 0 ≤ M, T ≤ 10000
Subtask 2 (11%): N = 1; 0 ≤ M, T ≤ 1000; 1 ≤ L ≤ 1000
Subtask 3 (13%): 1 ≤ N ≤ 10; all L = 1; 0 ≤ M, T ≤ 1000
Subtask 4 (17%): 1 ≤ N ≤ 10; all 0 ≤ T ≤ 10 are equal; 0 ≤ M ≤ 1000; 1 ≤ L ≤ 10
Subtask 5 (19%): 1 ≤ N ≤ 10; 0 ≤ M, T ≤ 10; 1 ≤ L ≤ 10
Subtask 6 (31%): 1 ≤ N ≤ 100; 0 ≤ M, T ≤ 100; 1 ≤ L ≤ 100
Subtask 7 (0%): Sample Testcase
For all testcases, 0 ≤ S ≤ 1000 and the maximum satisfaction possible in one day will not exceed the size of a 32-bit integer.
Sample Input
3
2 1
3 5
3 2
2 2
2 4
4 3
1 1
2 2
1 2
Sample Output
7
Explanation
On Day 3, Karl watches the (3, 5) show from Day 1 and the (1, 2) show from Day 3. This gains him 7 satisfaction.