← 返回题目列表

Codeforces · 1801/C

C. 音乐节

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

Vitya 有一个朋友 Masha,他非常想邀请她来参加他最喜欢的乐队表演的音乐节。然而,为了让朋友同意,她必须首先评估发布的新奇事物。 Vitya 知道,如果 Masha 听的歌曲比之前所有的歌曲都酷,她将获得 1 个单位的印象。不幸的是,专辑只能完整收听,而不能在某些地方更改其中的歌曲。

帮助Vitya找到这样的专辑顺序,以便玛莎的印象尽可能地好,她一定会和他一起去音乐节。

输入

每个测试由多个测试用例组成。第一行包含一个整数 t ($$$1 \le t \le 200\,000$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 200\,000$$$) — 专辑数量。

专辑描述如下。每个专辑的描述由两行组成:

第一行包含一个整数 $$$k_i$$$ ($$$1 \le k_i \le 200\,000$$$) — 第 $$$i$$$ 专辑中的曲目数量。

下面一行包含 $$$k_i$$$ 整数 $$$a_{i, 1},\ a_{i, 2},\ a_{i, 3},\ \ldots,\ a_{i, k_i}$$$ ($$$1 \le a_{i,j} \le 200\,000$$$) — 曲目中曲目的酷度$$$i$$$专辑。

表示 $$$\sum k_i$$$ 是所有 $$$k_i$$$ 的总和。保证 $$$\sum k_i \le 200\,000$$$。

输出

对于每个测试用例,打印单数——玛莎可以获得的最大印象。

示例

输入 #1

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

输出 #1

4
4

注意

在第一个测试示例中,最佳顺序是收听第四张、第二张、第三张和第一张专辑。

在这种情况下,玛莎将按以下顺序收听曲目:1; 7; 8、6; 4、9、4、6、8 将获得 4 个展示单位。

在第二个测试示例中,您必须首先听第一个,然后是第四个,然后以任意顺序听第二个和第三个。 在这种情况下,玛莎将获得最大的印象,并且对于第一张和第四张专辑中的每首歌来说,第二张和第三张专辑中没有任何歌曲。