Doorway

• 时间限制：2s
• 空间限制：1024MB

题目描述

liao 决定为八中机房设计一种多层滑动门。

门的每一层可以看作一条水平线段区间：左右两侧有实心墙作为边界，在两堵墙之间放置若干扇长度固定的滑动门。

在同一层中，每一扇门都可以独立向左或向右移动，但必须满足：不能与其他门重叠，也不能与墙重叠。所有层彼此平行，并在竖直方向上叠放。

门建好后，liao 发现一个问题：这扇门很难完全打开。由于预计会有大量学生通过，他希望制造一个尽可能大的开口，方便大家自由通行。

开口大小定义为：存在若干水平区间，使得对这些区间中的每一个点，在每一层上该点都既不被门覆盖、也不被墙阻挡。开口大小等于这些区间长度之和。

你的任务是，在允许对每一层的门进行移动的前提下，求能得到的最大开口大小。

输入格式

第一行一个整数 $n$ ——门的层数。

接下来 $n$ 行，每行的格式如下：

先给出三个整数 $k_i, x_{i,1}, x_{i,2}$（$0 \le x_{i,1} < x_{i,2} \le 10^9$）：

• 第 $i$ 层的滑动门数量为 $k_i$；
• 该层左右两堵墙的位置坐标分别为 $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}, l_{i,2}, \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}$）：

表示该层从最左边的门到最右边的门的顺序给出的各扇门的长度。

输出格式

输出一个整数——通过移动各层滑动门后，能得到的最大开口大小。

输入输出样例

输入 #1

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

输出 #1

4

输入 #2

见下发文件 doorway2.in。

输出 #2

见下发文件 doorway2.out。

说明

下图展示了样例 1 的一种最优方案：黑色为墙、灰色为门、白色为开口。把每一层的第一扇门尽量向左推，其余门尽量向右推，可以得到大小为 $4$ 的最大开口。

数据范围