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 秒内组装一条大链条。