Freedom of Choice
Contest: Codeforces Round 908 (Div. 1)
Difficulty rating: 2000
Tags: brute force, greedy, implementation

Let's define the anti-beauty of a multiset $$$\{b_1, b_2, \ldots, b_{len}\}$$$ as the number of occurrences of the number $$$len$$$ 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}, \ldots, c_{i, n_i}$$$ copies of the number $$$a_{i, n_i}$$$. It is guaranteed that $$$a_{i, 1} < a_{i, 2} < \ldots < a_{i, n_i}$$$. You are also given numbers $$$l_1, l_2, \ldots, l_m$$$ and $$$r_1, r_2, \ldots, r_m$$$ such that $$$1 \le l_i \le r_i \le c_{i, 1} + \ldots + 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:

1. Choose some $$$v_i$$$ such that $$$l_i \le v_i \le r_i$$$
2. Choose any $$$v_i$$$ numbers from the $$$i$$$-th multiset and add them to the multiset $$$X$$$.

You need to choose $$$v_1, \ldots, v_m$$$ and the added numbers in such a way that the resulting multiset $$$X$$$ has the minimum possible anti-beauty.

Input format:
Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 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 \le m \le 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 \le n_i \le 10^5, 1 \le l_i \le r_i \le c_{i, 1} + \ldots + c_{i, n_i} \le 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}, \ldots, a_{i, n_i}$$$ ($$$1 \le a_{i, 1} < \ldots < a_{i, n_i} \le 10^{17}$$$) — the distinct elements of the $$$i$$$-th multiset.

The third line of the block contains $$$n_i$$$ integers $$$c_{i, 1}, \ldots, c_{i, n_i}$$$ ($$$1 \le c_{i, j} \le 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 format:
For each test case, output the minimum possible anti-beauty of the multiset $$$X$$$ that you can achieve.

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

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

1. $$$\{10, 10, 10, 11, 11, 11, 12\}$$$. From this multiset, you need to select between $$$5$$$ and $$$6$$$ numbers.
2. $$$\{12, 12, 12, 12\}$$$. From this multiset, you need to select between $$$1$$$ and $$$3$$$ numbers.
3. $$$\{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$$$.

Example input:
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

Example output:
1
139
0
1
1
0
0

Editorial:
Note that after performing all operations, the multiset $$$X$$$ can have any integer size from $$$\sum l_i$$$ to $$$\sum r_i$$$. And the number of distinct numbers that can potentially be in $$$X$$$ is definitely not greater than $$$\sum n_i$$$. Therefore, if $$$\sum r_i - \sum l_i > \sum n_i$$$, there will always be a number from $$$\sum l_i$$$ to $$$\sum r_i$$$ that is not present in any of the $$$m$$$ given multisets, and thus will not be in $$$X$$$. By making $$$X$$$ of such size, we will have the anti-beauty of $$$X$$$ equal to $$$0$$$, which is the minimum achievable anti-beauty. So, if $$$\sum r_i - \sum l_i > \sum n_i$$$, we can output $$$0$$$ and terminate. Then we solve the problem under the condition $$$\sum r_i - \sum l_i \leq \sum n_i$$$.
$$$\sum n_i$$$ is limited to $$$10^5$$$. Therefore, we can explicitly iterate through all possible sizes of the multiset $$$X$$$, from $$$\sum l_i$$$ to $$$\sum r_i$$$, and for a fixed size $$$s$$$, determine the minimum anti-beauty if $$$X$$$ has size $$$s$$$. Then we take the minimum of these values as the answer.
For a fixed size $$$s$$$, to minimize the anti-beauty, we want to include as many numbers not equal to $$$s$$$ in $$$X$$$ as possible. For the multisets where $$$s$$$ is not present, we want to take $$$r_i$$$. To calculate this sum, we can take the sum of all $$$r_i$$$ and subtract from it the sum of $$$r_i$$$ for the multisets in which $$$s$$$ is present. And for those multisets where $$$s$$$ is present, we can explicitly iterate through them and use simple formulas to calculate how many $$$s$$$ we are obligated to take from each multiset. This will take at most $$$O(\sum n_i)$$$. For specific formulas, refer to the code.