题目描述

你在玩一个音游。

这个音游可以抽象为一个长度为 $m+1$ 的线段。

这个音游有 $n+m$ 秒，在前 $n$ 秒中，第 $i$ 秒会在 $1$ 处出现一个集合，这个集合可以用一个可重无序集 $S_i$ 来表示，大小为 $a_i$，每秒末尾这个集合的位置会增加 $1$。

因为你不会玩，所以你有一个可爱的 bot，它在第 $0$ 秒位于 $1$，之后每一秒你都需要选择一个值域区间 $[l,r]$，若这个 bot 所处位置有一个非空的集合 $Q$，那么 bot 会消去 $Q$ 中值域位于 $[l,r]$ 的数，该操作代价为 $r-l+1$。除此之外，这个 bot 在每秒的末尾可以选择将自己的位置 $+1$。

若有非空的集合到达 $m+1$ 处，那么你就失败了。请问在不失败的情况下你最少需要花费多少代价？

输入格式

第一行两个整数 $n,m$。

接下来 $n$ 行，每行第一个整数为 $a_i$，接下来有 $a_i$ 个整数，表示集合 $S_i$。

输出格式

一行一个整数，表示最小代价。

1 2
4 1 2 6 7

4

提示

设 $[1,k]$ 为集合中元素的值域。

本题采用捆绑测试。

• Subtask#1（$10\text{pts}$）：$m=1$；
• Subtask#2（$20\text{pts}$）：$n=1$；
• Subtask#3（$15\text{pts}$）：$k=100$；
• Subtask#4（$15\text{pts}$）：$m\le 100$；
• Subtask#5（$20\text{pts}$）：$m\le 10^5$；
• Subtask#6（$20\text{pts}$）：无特殊限制。

对于 $100\%$ 的数据，$1\le n\le 100$，$1\le m\le 10^9$，$1\le a_i\le 5\times 10^4$，除 Subtusk#3 外 $k=10^9$。