CF2181D Doorway

Nonsense 工程与研究大会大门的建造被委托给了一位未来的与会者，他决定采用多层推拉门的设计。 每一层可以描述为一个被实心墙壁限定的水平方向区间，其中包含若干长度固定的推拉门。在每一层中，每扇门都可以独立地向左或向右移动，只要不与其它门或墙壁重叠。所有层彼此平行，竖直堆叠。 完工后，组织者发现一个问题：大门很难完全打开。由于预计会有大量与会者，他们需要尽可能扩大开口，使所有人都能自由通过。 开口的大小定义为——在所有层中，每个该区间之内的点都没有门或墙所覆盖的所有水平区间长度之和。你的任务是，已知每层门的布局，求出可以实现的最大开口大小。

第一行包含一个整数 $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} < x_{i,2} \le 10^9$）开头，分别表示该层推拉门的数量以及该层左侧和右侧墙壁的 $x$ 坐标。$x_{i,1}$ 位置和 $x_{i,2}$ 位置各有一堵墙，$x < x_{i,1}$ 或 $x > 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$。

输出一行一个整数，表示通过移动每层推拉门可以获得的最大可能开口的大小。

下图显示了第一个样例的解法。墙体用黑色填充，门用不同深浅的灰色填充，开口部分为白色。当每层上的第一扇门全部靠左，剩下的门靠右移动时，可以获得宽度为 4 的最大开口。  由 ChatGPT 5 翻译