← 返回题目列表

Codeforces · 401/B

B. Sereja 和比赛

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

Sereja 是一名程序员,他喜欢参加 Codesorfes 回合。然而,乌日兰的互联网连接不太好,因此塞雷贾有时会跳过回合。

Codesorfes 有两种类型的回合:Div1(针对高级编码员)和 Div2(针对初级编码员)。 Div1 和 Div2 两轮比赛可以同时进行(Div1 比赛不能在没有 Div2 的情况下举行),在所有其他情况下,比赛时间不会重叠。每轮都有一个唯一的标识符——一个正整数。回合按回合开始时间用标识符顺序(无间隙)编号。同时进行的回合的标识符相差一个,并且 Div1 回合的标识符始终较大。

Sereja 是一名初级编码员,因此他只能参加 Div2 类型的回合。目前他正在参加 Div2 回合,其标识符等于 x。 Sereja 记得很清楚,在本轮之前他已经参加了整整 k 轮比赛。此外,他还记得他参加过的回合的所有标识符以及与这些回合同时进行的回合的所有标识符。塞雷贾不记得他错过的几轮比赛。

Sereja 想知道:他可能错过的 Div2 回合数最少和最多是多少?帮他找到这两个数字。

输入

第一行包含两个整数:x (1 ≤ x ≤ 4000) — Sereja 今天参加的回合,k (0 ≤ k < 4000) — 他参加的回合数。

接下来的 k 行包含 Sereja 之前参加的回合的描述。如果 Sereja 参加了同时进行的两轮比赛之一,则相应的行如下所示:“1 num2 num1”(其中 num2 是该 Div2 轮次的标识符,num1 是 Div1 轮次的标识符)。保证 num1 - num2 = 1。如果 Sereja 参加了通常的 Div2 回合,则相应的行如下所示:“2 num”(其中 num 是该 Div2 回合的标识符)。保证所有给定回合的标识符都小于x。

输出

在一行中打印两个整数——Sereja 可能错过的最小和最大轮数。

示例

输入 #1

3 2
2 1
2 2

输出 #1

0 0

输入 #2

9 3
1 2 3
2 8
1 4 5

输出 #2

2 3

输入 #3

10 0

输出 #3

5 9

注意

在第二个样本中,我们有第 1、6、7 轮未使用的标识符。Sereja 可能错过的最小轮数等于 2。在这种情况下,标识符为 1 的轮次将是通常的 Div2 轮次,标识符为 6 的轮次将与 Div1 轮次同步。

最大轮数等于 3。在这种情况下,所有未使用的标识符都属于通常的 Div2 轮。