思路

• 关键等价：整场比赛中被击败的战力序列必须严格递增（若上一次击败的是 $v$，则新战力为 $v+1$，下一次需选 $\ge v+1$ 的对手，等价于严格变大）。
• 同一层内可以任意选择对手并自由排序；跨层只能按层号递增的顺序进行。于是可以将每一层的数组升序排序后按层连接成序列 $S$。
• 问题化为：$S$ 的严格上升子序列（LIS）最大长度。初始战力为 $1$ 仅要求第一项 $\ge 1$，对任意 $a_{i,j}\ge 1$ 总是满足，因此不额外限制。
• 计算方法：对每层排序升序后拼接；对拼接序列做严格 LIS（“牌堆法”）：维护数组 $tails$，对每个值 $x$ 用二分下界（$lower_bound$）找到第一个 $\ge x$ 的位置替换；未找到则追加。最终答案为 $|tails|$。

正确性说明

题目内容

Tk 是一个战斗狂，秉承着战斗爽的理念，他隐藏了自己无敌的战力，现冒充一个毫无威胁的小萌新参加爬榜竞赛。裁判测试后，Tk 的初始战斗力定为 $1$ 。

比赛共有 $n$ 个分级，编号为 $1$ 至 $n$ ；第 $i$ 个分级包含 $m_i$ 名选手，其中第 $j$ 名选手的战斗力为 $a_{ij}$ 。

Tk 初始位于第 $1$ 个分级，比赛过程中，他会反复执行以下两种操作之一，直到无法继续。

• 在当前分级中，选择一名战斗力不低于自己当前战斗力的选手 $a_{ij}$ 并击败该选手；此时击败数加 $1$ ，且 Tk 的战斗力被重置为 $a_{ij}+1$ ；

• 如果此时分级编号不为 $n$ 选择进入下一个分级，即分级编号加 $1$ ；该操作不可逆，一旦进入无法返回。

Tk 对比赛本身不感兴趣，他只想知道最多可以击败多少名选手，请输出这个最大击败数。

输入描述

第一行输入一个整数 $n(1≦n≦10^4)$ ，表示分级数；

接下来 $n$ 行，第 $i$ 行首先输入一个整数 $m_i(1≦m_i≦2×10^5)$ ，表示第 $i$ 个分级的选手人数；随后输入 $m_i$ 个整数 $a_{i,1},a_{i,2},...,a_{i,m_i}(1≦a_{i,j}≦10^9)$ ，表示每位选手的战斗力；

除此之外，保证所有分级中 $m_i$ 之和不超过 $2×10^5$ 。

输出描述

输出一个整数，表示 Tk 在比赛中能够击败的最多选手数。

样例1

输入

2
2 1 8
4 2 3 4 5

输出

5

说明

对于此样例，在第一层击败战斗力为 $1$ 的人，Tk 战斗力重置为 $2$ ，前往第二层，在第二层击败战斗力为 $2$ 的人，战斗力重置为 $3$ ，在第二层击败战斗力为 $3$ 的人，战斗力重置为 $4$ ，在第二层击败战斗力为 $4$ 的人，战斗力重置为 $5$ ，在第二层击败战斗力为 $5$ 的人，战斗力重置为 $6$ 。

样例2

输入

2
2 1 1
3 2 2 2

输出

2