CF2181D.Doorway

The construction of the doorway for the Nonsense Engineering and Research Convention was delegated to one of the future attendees, who decided on a multi-layered sliding door design.

Each layer can be described as a horizontal interval, bounded by solid walls on the left and right, containing a number of sliding doors of fixed lengths. Within a layer, each door can move independently to the left or right, as long as it does not overlap other doors or the walls. All layers are parallel and stacked vertically.

After construction, the organizers noticed a problem: it is difficult to fully open the door, and since a large number of attendees are expected, they need to create the largest possible opening to allow everyone to pass through freely.

The size of the opening is defined as the total length of horizontal intervals such that, at every point of such an interval and in every layer, there is neither a door nor a wall. Your task is to determine the largest possible opening, given the doors' layout.

通往“荒谬工程与研究大会”会场的门道建设任务交由一位未来的参会者负责，他决定采用多层滑动门设计方案。

每一层可描述为一个水平区间，其左右两侧为实体墙，区间内包含若干固定长度的滑动门。在单一层内，每扇门均可独立地向左或向右滑动，但不得与其他门或墙体发生重叠。所有层彼此平行，并在垂直方向上堆叠。

建成后，组织方发现了一个问题：门难以完全开启；而由于预计参会人数众多，他们需要创造出尽可能大的开口，以便所有人能自由通行。

开口的大小定义为：满足如下条件的水平区间的总长度——该区间内任意一点，在每一层上均既无门也无墙。你的任务是：给定各层门的布局，求出可能的最大开口尺寸。

The first line contains an integer $n$ ($1 \le n \le 100\,000$) — the number of layers of the door.

Each of the next $n$ lines starts with three integers $k_i$, $x_{i,1}$, $x_{i,2}$ ($0 \le k_i \le 300\,000$; $0 \le x_{i,1} \lt x_{i,2} \le 10^9$) — the number of sliding doors on that layer and the $x$-coordinates $x_{i,1}$ and $x_{i,2}$ of the walls on that layer. There is a wall at $x_{i,1}$ and a wall at $x_{i,2}$; all positions with $x \lt x_{i,1}$ or $x \gt x_{i,2}$ are blocked by walls.

They are followed by $k_i$ integers $l_{i,1}, \ldots, l_{i,k_i}$ ($1 \le l_{i,j}$; $\sum\limits_{j=1}^{k_i} l_{i,j} \le x_{i,2} - x_{i,1}$) — the lengths of the sliding doors on that layer given in order from the leftmost door to the rightmost.

It is guaranteed that $\sum\limits_{i=1}^{n} k_i \le 300\,000$.

第一行包含一个整数 $n$（$1 \le n \le 100\,000$），表示门的层数。

接下来的 $n$ 行，每行以三个整数 $k_i$、$x_{i,1}$、$x_{i,2}$（$0 \le k_i \le 300\,000$；$0 \le x_{i,1} \lt x_{i,2} \le 10^9$）开头，分别表示该层滑动门的数量，以及该层两侧墙壁的 $x$ 坐标 $x_{i,1}$ 和 $x_{i,2}$。在位置 $x_{i,1}$ 和 $x_{i,2}$ 处各有一堵墙；所有满足 $x \lt x_{i,1}$ 或 $x \gt x_{i,2}$ 的位置均被墙壁封锁。

随后是 $k_i$ 个整数 $l_{i,1}, \ldots, l_{i,k_i}$（$1 \le l_{i,j}$；$\sum\limits_{j=1}^{k_i} l_{i,j} \le x_{i,2} - x_{i,1}$），表示该层上从左到右依次排列的各滑动门的长度。

保证 $\sum\limits_{i=1}^{n} k_i \le 300\,000$。

Output a single integer — the size of the largest possible opening that can be achieved by moving the sliding doors on each layer.

输出一个整数——通过移动每层的滑动门所能实现的最大开口尺寸。

This illustration shows a solution for the first example. Walls are filled with black color, doors are filled with various shades of grey, the opening is white. When first doors on each layer are shifted to the left and the rest of the doors to the right, we get the largest opening of 4.

该示意图展示了第一个样例的解法。墙壁用黑色填充，门用不同深浅的灰色填充，开口区域为白色。当将每层的第一个门向左移动、其余门向右移动时，可得到最大开口尺寸 4。