A16794 · Doorway · GESP考级

题目描述

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$。

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

输入 #1

2
2 2 11 3 2
3 4 12 1 1 2

输出 #1