T95684 [RC-01] 运货

很久以前，yltx 来到了某现代化工厂，并且注意到了一些奇怪的事情，然后出了这道水题。

该工厂是由机器人小车运货的。~~小车奇慢无比~~ 小车行驶在一个**单向的**椭圆形轨道上，所以当小车运动到 $n+1$ 的位置时，就视为它已经将货物卸下车并回到起点 $0$，**可以**（注意，不是必须）再次出发。 总共有 $n$ 个货架（分别在位置 $1$ 至 $n$ 处），每个货架上将会有 $a_i$ 个货，第 $j$ 个货物将在 $t_{i,j}$ 时出现在货架口。 当然，如果一个货物已经到达货架口，且它没有被运走，那么它就会挡住后面一个货物，哪怕后面一个已经到达了货架口，也只能先运输前一个。 小车接货、卸货都不要时间，并且每个小车速度都为一个长度单位每秒，每个小车一次最多只能装一个货物，而且由于单行，只能前进。所以现在 yltx 思考了 1ms 想想出一种方案合理安排 $m$ 个小车，使得送货时间最短。 他当然会做了~~人脑计算机不是吹的~~，于是他想和你对个答案。 注：除了第 $0$ 个位置，其他位置都不允许有小车重合。（意即：不准超车）

第一行两个整数 $n$，$m$。 接下来 $n$ 行，第 $i$ 行第一个整数 $a_{i}$，然后是 $a_{i}$ 个整数，表示 $ t_{i,j}$。

只有一行，包含一个整数，表示最少要花多长时间。

【样例解释】 对于样例 $1$，应让 $1$ 号小车接 $1$ 时刻的货物，然后让小车 $2$ 接 $5$ 时刻的货物。如果让小车 $1$ 去接 $5$ 时刻的货物，小车 $2$ 接 $1$ 时刻的货物，则会导致 $1$ 号车挡住 $2$ 号车。 对于样例 $2$，应让 $1$ 号小车越过时刻 $2$ 的货物去接时刻 $4$ 的，把 $2$ 时刻的货物留给 $2$ 号小车，也可以让 $1$ 号小车接时刻 $2$ 的货物，$2$ 号小车接时刻 $4$ 的，答案不变。 【数据范围】 对于所有数据，$1\le n\le 10^6$，$1\le m\le 10^3$，$0\le a_i\le 2000$，$0\le t_{i,j}\le 10^{15}$。详细数据范围见下表。 | 测试点编号 | $n$ | $m$ | $a_i$ | $t$| 分值 | |:---:|:---:|:---:|:---:|:---:|:---:| | #1 | $\le10$ | $\le5$ | $\le10$ | $\le10$ | $5$ | | #2 | $\le500$ | $\le50$ | $\le20$ | $\le500$ |$7$ | | #3 | $\le5\times10^3$ | $\le200$ | $\le 2000$ | $\le10^4$ |$10$ | | #4 | $\le10^4$ | $\le10$ | $\le300$ | $\le10^5$ |$15$ | | #5 | $\le2\times10^5$ | $\le200$ | $\le50$ | $\le10^7$ |$25$ | | #6 | $\le10^6$ | $\le10^3$ | $\le10$ | $\le10^{15}$ |$38$ | 输入数据保证同一个货架上，$t$ 升序。 **出题人善意的提醒：本题 I/O 量较大，请注意优化。**