注：下文中的 multiset 均为可重集。

我们定义一个大小为 $len$ 的 multiset 的不优美度为数 $len$ 在这个 multiset 里的出现次数。

给你 $m$ 个 multiset，第 $i$ 个 multiset 包含 $n_i$ 个不同的元素，具体的：这个 multiset 中含有 $c_{i,1}$ 个 $a_{i,1}$，$c_{i,2}$ 个 $a_{i,2}$，$\dots$，$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}$ 。

我们按照如下操作创建一个 multiset X，最初 X 为空。然后，对于 $1$ 到 $m$ 的每一个数 $i$，执行下面的操作：

1.选择一个数 $v_i$ 使得 $l_i \le v_i \le r_i$

2.从第 $i$ 个 multiset 里选择任意 $v_i$ 个数并把它们加入 X。

你的任务是选择 $v_1, \ldots, v_m$ ，使得 mutiset X 的不优美度最小。

多测，$1 \le t \le 10^4$ , $1 \le m \le 10^5$，$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}$，$1 \le a_{i, 1} < \ldots < a_{i, n_i} \le 10^{17}$， $1 \le c_{i, j} \le 10^{12}$ ，$m$ 的总和以及所有数据里的 $n_i$ 的总和不超过 $10^5$。

翻译来自@brimosta

已经提交翻译文本