题目背景

CF1801C

题目描述

小男孩维佳非常喜欢听音乐。他一直关注着自己喜欢的乐队，因此知道本周五将有 $n$ 张新专辑发布，第 $i$ 张专辑包含 $k_i$ 首曲目。当然，作为最忠实的粉丝，维佳已经提前听过了所有即将发布的新歌，并且知道第 $i$ 张专辑中第 $j$ 首歌的“酷炫度”为 $a_{i,j}$。

维佳有一个朋友玛莎，他非常希望邀请玛莎一起去参加有他最喜欢乐队出演的音乐节。不过要想让玛莎答应，玛莎需要先体验一下这些新歌。维佳知道，如果玛莎听到的某首歌酷炫度超过她此前听过的所有歌，她就会获得 $1$ 点“印象值”。遗憾的是，专辑只能整张播放，且专辑内歌曲顺序不能改变。

请帮助维佳安排专辑的播放顺序，使得玛莎获得的印象值尽可能大，这样她一定会答应和他一起去音乐节。

输入格式

第一行包含一个整数 $n$（$1 \le n \le 200\,000$），表示专辑数量。

接下来是 $n$ 组专辑描述。每组描述包含两行：

• 第一行包含一个整数 $k_i$（$1 \le k_i \le 200\,000$），表示第 $i$ 张专辑的曲目数。
• 第二行包含 $k_i$ 个整数 $a_{i, 1},\ a_{i, 2},\ \ldots,\ a_{i, k_i}$（$1 \le a_{i,j} \le 200\,000$），依次表示第 $i$ 张专辑每首歌的酷炫度。

记 $\sum k_i$ 为所有专辑曲目数之和。保证 $\sum k_i \le 200\,000$。

输出格式

输出一个整数，表示玛莎最多能获得的印象值。

4
5
4 9 4 6 8
1
7
2
8 6
1
1

4

4
2
3 4
2
1 8
2
2 8
2
7 9

4

提示

样例解释

在第一个测试样例中，最优的播放顺序是先听第 $4$ 张、再听第 $2$ 张、第 $3$ 张和第 $1$ 张专辑。这样玛莎依次听到的歌曲为：1；7；8, 6；4, 9, 4, 6, 8。玛莎将获得 $4$ 点印象值。

在第二个测试样例中，应先播放第 $1$ 张专辑，再播放第 $4$ 张，之后第 $2$ 和第 $3$ 张顺序任意。这样玛莎能获得最大印象值，且第 $1$ 和第 $4$ 张专辑的每首歌都能带来印象值，第 $2$ 和第 $3$ 张专辑则不会带来新的印象值。

评分说明

本题测试点分为 7 组。只有通过某一组所有测试点，且通过部分之前组所有测试点，才能获得该组分数。有些分组不要求通过样例测试点。

组别	分值	$n$	$k_i$	$a_{i, j}$	必须通过的组	备注
0		--		--	--	样例测试点
1	14	$n \le 7$	$\sum k_i \le 1000$		0
2	9	--	--	$a_{i, j} \le 2$	--
3	12			$a_{i, j} \le 10$	0, 2
4	15		$k_i \le 2$	--
5	13	$n \le 1000$	--	$a_{i, j} \le 1000$	0
6		$n \le 30\,000$		$a_{i, j} \le 30\,000$	0, 5
7	24	--		--	0--6