说明

洛谷网校共开设 $n$ 类课程，编号依次为 $1, 2, \cdots, n$。学员按照课程 $1, 2, \cdots, n$ 的顺序学完课程，可以在 FCC ION 比赛中取得好成绩。学习讲究循序渐进，在前一个课程学完前，不能开始下一个课程的学习。

小汪决定在接下来的 $m$ 天里在洛谷网校参与学习。接下来的 $m$ 天里，编号为 $i$ 的课程共有 $c_i$ 个班级，第 $j$ 个班级从第 $s_{i,j}$ 天开始，第 $t_{i,j}$ 天结束。

小汪需要从课程 $1$ 开始学习。且在任意一天，小汪只能属于一个班级。也就是说，假设小汪参加的课程 $3$ 的班级在第 $20$ 天结束，且有课程 $4$ 的一个班级在第 $20$ 天开始，小汪无法参加课程 $4$ 的这个班级。

现在，给出洛谷网校的开课计划，请问小汪最早在第多少天结束全部课程的学习。如果无法在 $m$ 天内学完，请输出 $-1$。

输入格式

第一行两个整数 $n,m$。

接下来 $n$ 行，第 $i$ 行描述课程 $i$ 的情况：

• 第一个整数为 $c_i$，表示班级的数目。
• 接下来 $2\cdot c_i$ 个整数，每两个整数描述一个班级，分别为 $s_{i,j}$ 与 $t_{i,j}$。

输出格式

输出一行一个整数，表示答案。

4 20
4 1 3 5 7 9 11 16 18
4 2 4 6 7 7 9 11 16
4 4 5 7 8 10 11 17 18
4 2 4 6 8 13 15 18 19

15

4 15
2 1 2 10 12
1 11 14
1 15 15
1 15 15

-1

提示

【样例 1 解释】

开班和学习情况如下图所示。黄色表示小汪所参加的班级。

【样例 2 解释】

在 $15$ 天内最多上完课程 $3$，无法完成课程 $4$。

【数据规模与约定】

对于 $30\%$ 的测试数据，$c_i=1$。

对于 $70\%$ 的测试数据，$1 \le n \le 30$，$1 \le s_{i, j} \le t_{i, j} \le m \le 10^5$，$1 \le c_i \le m$。

对于 $100\%$ 的测试数据，$1 \le n \le 10^5$，$1 \le s_{i, j} \le t_{i, j} \le m \le 10^9$，$1 \le c_i \le m$，$\sum c_i \le 10^5$。不保证对于任意的 $u<v$，$s_{i,u}\le s_{i,v}$，不保证对于任意的 $u<v$，$t_{i,u}\le t_{i,v}$。