#537. 安排时间

传统 3000 ms 1024 MiB
标准 IO
文本比较 dd 标签

题目描述

小 M 是车南大学 J8241 班的班长,学院的辅导员希望小 M 找到一段时间来给全班同学做一次团建活动。

这可难坏了小 M,因为大家的课表几乎是各不相同的。

为了完成这个任务,小 M 将一周的时间分为了 mm 段,接着,她拿到了全班 nn 个同学的时间安排表,每个同学会在时间安排表上写上自己的空闲时间段。

小 M 希望能够找出 11时间举行团建活动,使得在缺席的同学尽可能的少的情况下,尽可能早的进行,你能帮帮小 M 吗?

输入格式

第一行 22 个整数 n,m(1n,m105n, m(1\le n,m\le 10^5),表示同学的个数和时间的段数。

接下来 nn 行,第 i+1i+1 行先是一个整数 pi(1pi10)p_i(1\le p_i\le10),表示这名同学的空闲时间段数。紧接着 2×pi2\times p_i 个整数 li,j,ri,j(1li,1ri,1<li,2ri,2<li,piri,pim)l_{i, j}, r_{i,j}(1\le l_{i,1}\le r_{i,1}< l_{i,2}\le r_{i,2}\cdots < l_{i,p_i}\le r_{i,p_i}\le m),表示这名同学在 [li,j,ri,j][l_{i,j}, r_{i,j}] 这一整段时间有空。

输出格式

11 行两个整数 t,xt, x,分别表示最早的时间和缺席的人数。

样例

输入样例

4 10
2 2 6 8 8
1 1 5
3 1 1 3 3 9 9
1 3 7

输出样例

3 0