无意义工程与研究大会的门口建造工作委托给了一位未来的与会者,他决定采用多层滑动门设计。
每层都可以描述为一个水平区间,左右以实心墙为界,包含许多固定长度的滑动门。在一层内,每扇门都可以独立向左或向右移动,只要它不与其他门或墙壁重叠即可。所有层都是平行并垂直堆叠的。
施工结束后,主办方注意到一个问题:门很难完全打开,而且由于预计参会人数较多,因此需要创造尽可能大的开口,以便大家自由通行。
开口的尺寸定义为水平间隔的总长度,使得在该间隔的每个点和每一层中既没有门也没有墙。您的任务是根据门的布局确定最大的可能开口。
输入
第一行包含一个整数 $$$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} \lt x_{i,2} \le 10^9$$$) — 该层上滑动门的数量以及该层上墙壁的 $$$x$$$ 坐标 $$$x_{i,1}$$$ 和 $$$x_{i,2}$$$。 $$$x_{i,1}$$$ 处有一堵墙,$$$x_{i,2}$$$ 处有一堵墙;所有带有 $$$x \lt x_{i,1}$$$ 或 $$$x \gt 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$$$。
输出
输出一个整数 - 通过移动每层上的滑动门可以实现的最大可能开口的大小。
示例
输入复制
22 2 11 3 23 4 12 1 1 2
输出复制
4
输入复制
22 0 7 2 41 4 9 4
输出复制
0
注意
该图显示了第一个示例的解决方案。墙壁充满了黑色,门充满了各种深浅的灰色,开口是白色的。当每层的第一扇门向左移动,其余的门向右移动时,我们得到最大的开口 4。