题目描述

在可爱的智程星网校中，小智准备开启自己的学习冒险之旅啦！🐾

网校一共开设了 $n$ 门课程，编号为 $1,2,\cdots,n$。
为了在最终的比赛中取得好成绩，小智必须按照顺序学习课程，也就是说：

• 必须先学完课程 $1$ 才能学课程 $2$
• 必须先学完课程 $2$ 才能学课程 $3$
• ……依次类推 🎯

接下来共有 $m$ 天的学习时间 ⏰

对于第 $i$ 门课程，一共有 $c_i$ 个班级可以选择。
第 $j$ 个班级的上课时间为：从第 $s_{i,j}$ 天开始，到第 $t_{i,j}$ 天结束 📅

但是，小智有一个限制： 👉 在任意一天，只能参加一个班级！ 也就是说，如果某门课的班级在第 $x$ 天结束，而下一门课的班级在第 $x$ 天开始，那么这个班级是不能选的！（必须严格错开）⚠️ 现在，小智想尽可能快地完成所有课程学习 🏁 请你帮他计算：最早在第多少天可以完成所有课程？ 如果在 $m$ 天内无法完成全部课程，则输出 $-1$ ❌

输入格式

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

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

• 第一个整数为 $c_i$
• 接下来 $2\cdot c_i$ 个整数，每两个为一组 $(s_{i,j}, t_{i,j})$

输出格式

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

输入输出样例 #1

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

输入输出样例 #2

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

-1

样例解释

【样例 1 解释】

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

【样例 2 解释】

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

说明

小智必须保证时间严格递增：如果上一门课程结束时间为 $T$， 那么下一门课程必须满足：$s_{next} > T$否则无法参加该班级 ⚠️

数据范围

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

对于 $70\%$ 的数据：

• $1 \le n \le 30$
• $1 \le s_{i,j} \le t_{i,j} \le m \le 10^5$

对于 $100\%$ 的数据：

• $1 \le n \le 10^5$
• $1 \le s_{i,j} \le t_{i,j} \le m \le 10^9$
• $所有c_i的和 \le 10^5$且不保证班级时间有序 🚫