Description

In the SCU training team, Mr. Shen loves eating very much. Every time before training, he would say, when we eat dinner today? But of course, besides these, he is a very good cook. One day, a guest visited the SCU training team, and as a cook, Mr. Shen would cook dinner that day. There were n dishes, and Mr. Shen knew that how the guest likes these dishes, for the dish i,it was l[i]. And for the dish i , Mr. Shen need r[i] energy to finish it. And for the consideration of nutrition, if Mr. Shen chose the dish i, then he must cook dish t[1],t[2]Mr. Shen wanted to know what is the maximum of (l[i]-r[i]) (i(S),S indicates the set of dishes Mr. Shen chose) .

Input

The first line contains an integer T(T<=10), indicating T test cases.

For each test case, the first line contains an integer n (n<=250), indicating there were n dishes. The next n lines each contains two integers l[i], r[i], indicating how the gusts likes the dish i and how much energy it need to cook this dish.( 0 < r[i], l[l] <= 100) The next n lines each contains x+1 integers,the first number (x) of the i-th line indicate you should choose the next x dishes (t[0], t[1] ... t[x-1])if you want to choose the i-th dish ( 0 < t[i] <= n ) .

Output

For each test case, output an integer, indicating the result Mr. Shen wanted to know

Sample Input

2
2
10 1
1 2
1 2
0
2
10 1
1 2
0
0

Sample Output

8
9

Author

liulf