Freedom of Choice Solution Codeforces

Let’s define the anti-beauty of a multiset ${b_{1}, b_{2}, \dots, b_{l e n}}$ as the number of occurrences of the number $l e n$ in the multiset.

You are given $m$ multisets, where the $i$ -th multiset contains $n_{i}$ distinct elements, specifically: $c_{i, 1}$ copies of the number $a_{i, 1}$ , $c_{i, 2}$ copies of the number $a_{i, 2}, \dots, c_{i, n_{i}}$ copies of the number $a_{i, n_{i}}$ . It is guaranteed that $a_{i, 1} < a_{i, 2} < \dots < a_{i, n_{i}}$ . You are also given numbers $l_{1}, l_{2}, \dots, l_{m}$ and $r_{1}, r_{2}, \dots, r_{m}$ such that $1 \leq l_{i} \leq r_{i} \leq c_{i, 1} + \dots + c_{i, n_{i}}$ .

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

Choose some $v_{i}$ such that $l_{i} \leq v_{i} \leq r_{i}$
Choose any $v_{i}$ numbers from the $i$ -th multiset and add them to the multiset $X$ .

You need to choose $v_{1}, \dots, v_{m}$ 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$ ( $1 \leq t \leq 10^{4}$ ) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $m$ ( $1 \leq m \leq 10^{5}$ ) — the number of given multisets.

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

The first line of each block contains three integers $n_{i}, l_{i}, r_{i}$ ( $1 \leq n_{i} \leq 10^{5}, 1 \leq l_{i} \leq r_{i} \leq c_{i, 1} + \dots + c_{i, n_{i}} \leq 10^{17}$ ) — 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 $n_{i}$ integers $a_{i, 1}, \dots, a_{i, n_{i}}$ ( $1 \leq a_{i, 1} < \dots < a_{i, n_{i}} \leq 10^{17}$ ) — the distinct elements of the $i$ -th multiset.

The third line of the block contains $n_{i}$ integers $c_{i, 1}, \dots, c_{i, n_{i}}$ ( $1 \leq c_{i, j} \leq 10^{12}$ ) — 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 $10^{5}$ , and also the sum of $n_{i}$ for all blocks of all test cases does not exceed $10^{5}$ .

Output

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

Example

input

Copy

3 5 6

10 11 12

3 3 1

1 1 3

2 4 4

12 13

1 5

7 1000 1006

1000 1001 1002 1003 1004 1005 1006

147 145 143 143 143 143 142

2 48 50

48 50

25 25

1 1 1

2 1 1

1 2

1 1

4 8 10

11 12 13 14

3 3 3 3

2 3 4

11 12

2 2

output

Copy

Note

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

${10, 10, 10, 11, 11, 11, 12}$ . From this multiset, you need to select between $5$ and $6$ numbers.
${12, 12, 12, 12}$ . From this multiset, you need to select between $1$ and $3$ numbers.
${12, 13, 13, 13, 13, 13}$ . From this multiset, you need to select $4$ numbers.

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

Leave a Comment Cancel reply