题目描述

题目来源：「RCOI2019」Rochine Round 1

很久以前，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

2 2
1 1
1 5

6

对于样例 $1$，应让 $1$ 号小车接 $1$ 时刻的货物，然后让小车 $2$ 接 $5$ 时刻的货物。如果让小车 $1$ 去接 $5$ 时刻的货物，小车 $2$ 接 $1$ 时刻的货物，则会导致 $1$ 号车挡住 $2$ 号车。

18 7
1 1
1 1
5 1 5 11 31 39
1 29
5 11 34 41 45 47
1 37
6 15 31 39 41 41 47
1 47
1 39
3 1 1 21
1 23
1 11
1 37
5 1 3 9 11 16
5 1 1 11 18 31
3 1 31 33
1 41
9 1 1 1 1 11 35 41 41 45

152

数据范围与提示

对于所有数据，$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}$。详细数据范围见下表。

输入数据保证同一个货架上，$t$ 升序。

出题人善意的提醒：本题 I/O 量较大，请注意优化。