P14785 [NERC 2025] 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_{i,1}$ 和 $x_{i,2}$ 处各有一堵墙；所有满足 $x < x_{i,1}$ 或 $x > x_{i,2}$ 的位置都被墙壁阻挡。 随后跟着 $k_i$ 个整数 $l_{i,1}, \dots, l_{i,k_i}$ ($1 \le l_{i,j}$；$\sum_{j=1}^{k_i} l_{i,j} \le x_{i,2} - x_{i,1}$) —— 该层滑动门的长度，按从左到右的顺序给出。 保证 $\sum_{i=1}^{n} k_i \le 300\,000$。

输出一个整数 —— 通过移动各层的滑动门可以实现的最大可能开口的大小。

这张图展示了第一个示例的一种解决方案。墙壁用黑色填充，门用不同的灰色阴影填充，开口为白色。当每层的第一扇门向左移动，其余门向右移动时，我们得到最大的开口 $4$。 :::align{center}  :::