← 返回题目列表

Codeforces · 2181/D

D. 门口

中文机器翻译题面 查看原题

无意义工程与研究大会的门口建造工作委托给了一位未来的与会者,他决定采用多层滑动门设计。

每层都可以描述为一个水平区间,左右以实心墙为界,包含许多固定长度的滑动门。在一层内,每扇门都可以独立向左或向右移动,只要它不与其他门或墙壁重叠即可。所有层都是平行并垂直堆叠的。

施工结束后,主办方注意到一个问题:门很难完全打开,而且由于预计参会人数较多,因此需要创造尽可能大的开口,以便大家自由通行。

开口的尺寸定义为水平间隔的总长度,使得在该间隔的每个点和每一层中既没有门也没有墙。您的任务是根据门的布局确定最大的可能开口。

输入

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

输出

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

示例

输入
复制

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

输出
复制

4

输入
复制

2
2 0 7 2 4
1 4 9 4

输出
复制

0

注意

该图显示了第一个示例的解决方案。墙壁充满了黑色,门充满了各种深浅的灰色,开口是白色的。当每层的第一扇门向左移动,其余的门向右移动时,我们得到最大的开口 4。