CF1893C Freedom of Choice

我们定义一个多重集 $ \{b_1, b_2, \ldots, b_{len}\} $ 的“反美丽值”为该多重集中数字 $ 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 $ 的反美丽值尽可能小。

每组测试数据包含多组测试用例。第一行包含一个整数 $ 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 $ 个多重集中不同数字的个数，以及从第 $ 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} $），表示每个元素的出现次数。 保证所有测试用例中 $ m $ 的总和不超过 $ 10^5 $，所有测试用例中所有 $ n_i $ 的总和不超过 $ 10^5 $。

对于每组测试用例，输出一个整数，表示你能得到的多重集 $ X $ 的最小反美丽值。

在第一个测试用例中，多重集如下： 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 $ 次，所以反美丽值为 $ 1 $。可以证明无法得到更小的反美丽值。 由 ChatGPT 4.1 翻译