← 返回题目列表

Codeforces · 555/A

A. 俄罗斯套娃案例

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

Android 安德鲁是一位银河系著名的侦探。他现在正在调查当代艺术展览中的破坏行为案件。

主要展品是由 n 个俄罗斯套娃组成的结构,可以相互嵌套。俄罗斯套娃的编号是从 1 到 n。编号较小的套娃可以嵌套在编号较大的套娃中,两个套娃不能直接嵌套在同一个娃娃中,但可以存在链式嵌套,例如1 → 2 → 4 → 5。

在一秒钟内,您可以执行以下两个操作之一:

- 拥有一个未嵌套在任何其他套娃中的套娃 a 和一个套娃 b,使得 b 不包含任何其他套娃且不嵌套在任何其他套娃中,您可以将 a 放入 b 中;
- 俄罗斯套娃 a 直接包含在俄罗斯套娃 b 中,这样 b 不会嵌套在任何其他俄罗斯套娃中,您可以从 b 中得到 a。

根据现代审美规范,展出的俄罗斯套娃以特定的配置组装在一起,即作为几条独立的嵌套俄罗斯套娃链,但犯罪分子按照神秘的计划取出所有娃娃并将它们组装成一条大链(1 → 2 → ... → n)。为了继续调查,Andrewid 需要知道可以在最短的时间内执行此操作。

输入

第一行包含整数 n (1 ≤ n ≤ 105) 和 k (1 ≤ k ≤ 105) — 初始配置中的俄罗斯套娃和俄罗斯套娃链的数量。

接下来的 k 行包含对链的描述:第 i 行首先包含数字 mi (1 ≤ mi ≤ n),然后是 mi 数字 ai1, ai2, ..., aimi — 链中套娃的数量(套娃 ai1 嵌套在套娃 ai2 中,套娃 ai2 嵌套在套娃 ai3 中,依此类推,直到套娃aimi 未嵌套在任何其他 matryoshka 中)。

保证m1 + m2 + ... + mk = n,所有链中套娃的数量不同,每个链中套娃的数量按升序排列。

输出

在单行中打印从初始配置组装一条大链所需的最少秒数。

示例

输入 #1

3 2
2 1 2
1 3

输出 #1

1

输入 #2

7 3
3 1 3 7
2 2 5
2 4 6

输出 #2

10

注意

在第一个示例测试中,有两条链:1 → 2 和 3。在一秒钟内,您可以将第一个链嵌套到第二个链中,并得到 1 → 2 → 3。

在第二个样本测试中,您需要在 2 + 1 + 1 = 4 秒内将所有三个链条拆卸成单独的套娃,然后在 6 秒内组装一条大链条。