CF1893C.Freedom of Choice

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} \lt a_{i, 2} \lt \ldots \lt 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.

我们定义多重集 $\{b_1, b_2, \ldots, b_{\text{len}}\}$ 的**反美感（anti-beauty）**为该多重集中元素 $\text{len}$ 出现的次数。

给定 $m$ 个多重集，其中第 $i$ 个多重集包含 $n_i$ 个互不相同的元素，具体为：数字 $a_{i,1}$ 出现 $c_{i,1}$ 次，数字 $a_{i,2}$ 出现 $c_{i,2}$ 次，……，数字 $a_{i,n_i}$ 出现 $c_{i,n_i}$ 次。保证 $a_{i,1} < a_{i,2} < \ldots < a_{i,n_i}$。同时给定数组 $l_1, l_2, \ldots, l_m$ 和 $r_1, r_2, \ldots, r_m$，满足 $1 \le l_i \le r_i \le c_{i,1} + \ldots + c_{i,n_i}$。

我们构造一个初始为空的多重集 $X$。然后，对每个 $i$ 从 $1$ 到 $m$，必须且仅执行一次以下操作：

1. 选择某个整数 $v_i$，满足 $l_i \le v_i \le r_i$；
2. 从第 $i$ 个多重集中任选 $v_i$ 个数，加入多重集 $X$。

你需要恰当地选择 $v_1, \ldots, v_m$ 以及每次所选的具体数字，使得最终得到的多重集 $X$ 的反美感尽可能小。

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} \lt \ldots \lt 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$.

每个测试包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $m$（$1 \le m \le 10^5$），表示给定的多重集数量。

接着，对每个 $i$（从 $1$ 到 $m$），输入一个由三行组成的数据块。

每个数据块的第一行包含三个整数 $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}$），分别表示第 $i$ 个多重集中不同元素的个数，以及从该多重集中向集合 $X$ 添加元素个数的上下界。

每个数据块的第二行包含 $n_i$ 个整数 $a_{i, 1}, \ldots, a_{i, n_i}$（$1 \le a_{i, 1} \lt \ldots \lt a_{i, n_i} \le 10^{17}$），表示第 $i$ 个多重集中的互异元素。

每个数据块的第三行包含 $n_i$ 个整数 $c_{i, 1}, \ldots, c_{i, n_i}$（$1 \le c_{i, j} \le 10^{12}$），表示第 $i$ 个多重集中各元素的副本数量。

保证所有测试用例中 $m$ 的总和不超过 $10^5$，且所有测试用例中所有数据块的 $n_i$ 总和也不超过 $10^5$。

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

对于每个测试用例，输出你能达到的多重集 $X$ 的最小可能反美感值。

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$.

在第一个测试用例中，多重集合具有以下形式：

1. ${10, 10, 10, 11, 11, 11, 12}$。从该多重集合中，你需要选出 $5$ 到 $6$ 个数。
2. ${12, 12, 12, 12}$。从该多重集合中，你需要选出 $1$ 到 $3$ 个数。
3. ${12, 13, 13, 13, 13, 13}$。从该多重集合中，你需要选出 $4$ 个数。

你可以从第一个多重集合中选出元素 ${10, 11, 11, 11, 12}$，从第二个多重集合中选出 ${12}$，从第三个多重集合中选出 ${13, 13, 13, 13}$。于是，$X = {10, 11, 11, 11, 12, 12, 13, 13, 13, 13}$。集合 $X$ 的大小为 $10$，数字 $10$ 在 $X$ 中恰好出现 $1$ 次，因此 $X$ 的反美观度为 $1$。可以证明，无法得到小于 $1$ 的反美观度。