让我们将多重集 $$$\{b_1, b_2, \ldots, b_{len}\}$$$ 的反美定义为数字 $$$len$$$ 在多重集中出现的次数。
给定您 $$$m$$$ 多重集,其中第 $$$i$$$ 多重集包含 $$$n_i$$$ 不同元素,具体来说: $$$c_{i, 1}$$$ 数字 $$$a_{i,1}$$$ 副本,$$$c_{i, 2}$$$ 数字 $$$a_{i,2} 副本, \ldots, c_{i, n_i}$$$ 数字 $$$a_{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$$$,最初是空的。然后,对于从 $$$1$$$ 到 $$$m$$$ 的每个 $$$i$$$,您必须执行以下操作一次:
1. 选择一些 $$$v_i$$$ 使得 $$$l_i \le v_i \le r_i$$$
2. 从第 $$$i$$$ 个多重集中选择任何 $$$v_i$$$ 数字,并将它们添加到多重集 $$$X$$$ 中。
您需要选择 $$$v_1、\ldots、v_m$$$ 以及添加的数字,使得生成的多重集 $$$X$$$ 具有尽可能小的反美性。
输入
每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$m$$$ ($$$1 \le m \le 10^5$$$) — 给定多重集的数量。
然后,对于从$$$1$$$到$$$m$$$的每个$$$i$$$,输入由三行组成的数据块。
每个块的第一行包含三个整数 $$$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$$$ 个多重集以及要从第 $$$i$$$ 个多重集添加到 $$$X$$$ 的元素数量限制。
该块的第二行包含 $$$n_i$$$ 整数 $$$a_{i, 1}, \ldots, a_{i, n_i}$$$ ($$$1 \le a_{i, 1} < \ldots < 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$$$。
输出
对于每个测试用例,输出您可以实现的多重集 $$$X$$$ 的最小可能反美。
示例
输入 #1
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
输出 #1
1 139 0 1 1 0 0
注意
在第一个测试用例中,多重集具有以下形式:
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$$$ 的反美。