无意义工程与研究大会（Nonsense Engineering and Research Convention）的门口建设工作被委托给了一位未来的参会者，他决定采用多层滑动门的设计。

每一层都可以描述为一个水平区间，左右两侧由实体墙限制，中间包含若干扇固定长度的滑动门。在同一层内，每扇门都可以独立地向左或向右移动，只要它不与其他门或墙壁重叠。所有层都是平行的，并且垂直堆叠。

建成后，组织者发现了一个问题：很难将门完全打开。由于预计会有大量参会者，他们需要创造一个尽可能大的通道，以便让所有人自由通过。

通道的大小定义为满足以下条件的水平区间的总长度：在该区间的任意点处，且在每一层中，既没有门也没有墙。给定门的布局，你的任务是确定可能的最大通道大小。

输入格式

第一行包含一个整数 $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$。

输出格式

输出一个整数 —— 通过移动每层上的滑动门所能达到的最大通道大小。

样例

输入样例 1

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

输出样例 1

4

输入样例 2

2
2 0 7 2 4
1 4 9 4

输出样例 2

0

说明

下图展示了第一个样例的一种解法。墙壁用黑色填充，门用不同深浅的灰色填充，通道为白色。当每层的第一扇门向左移动，其余的门向右移动时，我们得到了最大大小为 4 的通道。