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.