题目描述

某培训机构共开设 $n$ 类课程，编号依次为 $1, 2, \cdots, n$。学员需要按照课程 $1, 2, \cdots, n$ 的顺序依次完成所有课程，才能获得结业证书。学习讲究循序渐进，在前一门课程完成前，不能开始下一门课程的学习。

学员小凯计划在接下来的 $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 解释】

小凯选择的班级如下：

• 课程 1：选择班级 $[1, 3]$（第 1~3 天）
• 课程 2：选择班级 $[4, 6]$（第 4~6 天）
• 课程 3：选择班级 $[7, 8]$（第 7~8 天）
• 课程 4：选择班级 $[8, 13]$ 不可行（第 8 天冲突），选择 $[13, 15]$（第 13~15 天）

最终在第 15 天完成全部课程。

【样例 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\lt v$，$s_{i,u}\le s_{i,v}$，不保证对于任意的 $u\lt v$，$t_{i,u}\le t_{i,v}$。