艾玛喜欢玩积木。她有几个相同大小的立方体块,编号为 不同 上面写着 整数。她通过垂直堆叠这些积木来组装塔。
她的游戏配置是她用积木组装的一组塔。 Emma 可以对塔的配置执行两种操作:
- 分裂 任何具有多个方块的塔,通过从塔顶取出任意数量的方块并将它们移动到新塔并保持其顺序,以便旧塔的顶部方块成为新塔的顶部方块。此操作的结果是,塔的数量增加了一座。
- 结合 任意两座塔,方法是按相同顺序将一座塔中的方块移动到另一座塔的顶部。此操作的结果是,塔的数量减少了一座。
艾玛想要将所有块堆叠到一个塔中,以便所有块都按数字排序 - 从顶部数字最小的块到底部数字最大的块。艾玛希望尽可能少地进行拆分和组合操作。你的任务是找到她必须进行的最少操作数,并输出需要多少次拆分和组合。
输入
输入文件的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10\,000$$$) — 初始配置中的塔数。接下来的 $$$n$$$ 行描述了塔。每个塔 $$$i$$$ 由一行以数字 $$$k_i$$$ ($$$k_i \ge 1$$$; $$$\sum_1^n{k_i} \le 10\,000$$$) 开头的行描述 - 塔中的块数,后跟 $$$k_i$$$ 数字 $$$b_{i,j}$$$ ($$$1 \le b_{i,j} \le 10^9$$$) — 第 $$$i$$$ 塔中的块上写的数字,从上到下列出。输入中列出的所有块编号都不同。
输出
输出一行,其中包含两个整数 $$$s$$$ 和 $$$c$$$ - Emma 应该进行的拆分和组合操作的数量,以得到一个塔,其中块按其数量排序,从而使操作总数最小化。
示例
输入复制
2 3 3 5 8 2 9 2
输出复制
1 2
注意
该示例需要以下操作(1 个拆分和 2 个组合)。
![]() | ![]() | ![]() | ![]() |
| 初始 | 最后拆分 | 将第二个合并到第一个 | 合并第一到第二 |



