# Freedom of Choice Solution Codeforces

## Freedom of Choice Solution Codeforces

time limit per test

3 seconds

memory limit per test

512 megabytes

input

standard input

output

standard output

Let’s define the anti-beauty of a multiset {b1,b2,,blen}{�1,�2,…,����} as the number of occurrences of the number len��� in the multiset.

You are given m multisets, where the i-th multiset contains ni�� distinct elements, specifically: ci,1��,1 copies of the number ai,1��,1ci,2��,2 copies of the number ai,2,,ci,ni��,2,…,��,�� copies of the number ai,ni��,��. It is guaranteed that ai,1<ai,2<<ai,ni��,1<��,2<…<��,��. You are also given numbers l1,l2,,lm�1,�2,…,�� and r1,r2,,rm�1,�2,…,�� such that 1lirici,1++ci,ni1≤��≤��≤��,1+…+��,��.

Let’s create a multiset X, initially empty. Then, for each i from 11 to m, you must perform the following action exactly once:

1. Choose some vi�� such that liviri��≤��≤��
2. Choose any vi�� numbers from the i-th multiset and add them to the multiset X.

You need to choose v1,,vm�1,…,�� and the added numbers in such a way that the resulting multiset X has the minimum possible anti-beauty.

Input

Each test consists of multiple test cases. The first line contains a single integer t (1t1041≤�≤104) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer m (1m1051≤�≤105) — the number of given multisets.

Then, for each i from 11 to m, a data block consisting of three lines is entered.

The first line of each block contains three integers ni,li,ri��,��,�� (1ni105,1lirici,1++ci,ni10171≤��≤105,1≤��≤��≤��,1+…+��,��≤1017) — the number of distinct numbers in the i-th multiset and the limits on the number of elements to be added to X from the i-th multiset.

The second line of the block contains ni�� integers ai,1,,ai,ni��,1,…,��,�� (1ai,1<<ai,ni10171≤��,1<…<��,��≤1017) — the distinct elements of the i-th multiset.

The third line of the block contains ni�� integers ci,1,,ci,ni��,1,…,��,�� (1ci,j10121≤��,�≤1012) — the number of copies of the elements in the i-th multiset.

It is guaranteed that the sum of the values of m for all test cases does not exceed 105105, and also the sum of ni�� for all blocks of all test cases does not exceed 105105.

Output

For each test case, output the minimum possible anti-beauty of the multiset X that you can achieve.

Example
input

Copy
7
3
3 5 6
10 11 12
3 3 1
1 1 3
12
4
2 4 4
12 13
1 5
1
7 1000 1006
1000 1001 1002 1003 1004 1005 1006
147 145 143 143 143 143 142
1
2 48 50
48 50
25 25
2
1 1 1
1
1
1 1 1
2
1
1
1 1 1
1
2
2
1 1 1
1
1
2 1 1
1 2
1 1
2
4 8 10
11 12 13 14
3 3 3 3
2 3 4
11 12
2 2
output

Copy
1
139
0
1
1
0
0

Note

In the first test case, the multisets have the following form:

1. {10,10,10,11,11,11,12}{10,10,10,11,11,11,12}. From this multiset, you need to select between 55 and 66 numbers.
2. {12,12,12,12}{12,12,12,12}. From this multiset, you need to select between 11 and 33 numbers.
3. {12,13,13,13,13,13}{12,13,13,13,13,13}. From this multiset, you need to select 44 numbers.

You can select the elements {10,11,11,11,12}{10,11,11,11,12} from the first multiset, {12}{12} from the second multiset, and {13,13,13,13}{13,13,13,13} from the third multiset. Thus, X={10,11,11,11,12,12,13,13,13,13}�={10,11,11,11,12,12,13,13,13,13}. The size of X is 1010, the number 1010 appears exactly 11 time in X, so the anti-beauty of X is 11. It can be shown that it is not possible to achieve an anti-beauty less than 11.