← 返回题目列表

Codeforces · 1773/E

E. 易于组装

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

艾玛喜欢玩积木。她有几个相同大小的立方体块,编号为 不同 上面写着 整数。她通过垂直堆叠这些积木来组装塔。

她的游戏配置是她用积木组装的一组塔。 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 个组合)。

初始最后拆分将第二个合并到第一个合并第一到第二