#1527. 「RCOI2019」运货

「RCOI2019」运货

题目描述

题目来源:「RCOI2019」Rochine Round 1

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

该工厂是由机器人小车运货的。小车奇慢无比

小车行驶在一个单向的椭圆形轨道上,所以当小车运动到 n+1n+1 的位置时,就视为它已经将货物卸下车并回到起点 00可以(注意,不是必须)再次出发。

总共有 nn 个货架(分别在位置 11nn 处),每个货架上将会有 aia_i 个货,第 jj 个货物将在 ti,jt_{i,j} 时出现在货架口。

当然,如果一个货物已经到达货架口,且它没有被运走,那么它就会挡住后面一个货物,哪怕后面一个已经到达了货架口,也只能先运输前一个。

小车接货、卸货都不要时间,并且每个小车速度都为一个长度单位每秒,每个小车一次最多只能装一个货物,而且由于单行,只能前进。所以现在 yltx 思考了 1ms 想想出一种方案合理安排 mm 个小车,使得送货时间最短。

他当然会做了人脑计算机不是吹的,于是他想和你对个答案。

注:除了第 00 个位置,其他位置都不允许有小车重合。(意即:不准超车)

输入格式

第一行两个整数 nnmm

接下来 nn 行,第 ii 行第一个整数 aia_{i},然后是 aia_{i} 个整数,表示 ti,j t_{i,j}

输出格式

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

样例 1

2 2
1 1
1 5
6

对于样例 11,应让 11 号小车接 11 时刻的货物,然后让小车 2255 时刻的货物。如果让小车 11 去接 55 时刻的货物,小车 2211 时刻的货物,则会导致 11 号车挡住 22 号车。

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

数据范围与提示

对于所有数据,1n1061\le n\le 10^61m1031\le m\le 10^30ai20000\le a_i\le 20000ti,j10150\le t_{i,j}\le 10^{15}。详细数据范围见下表。

测试点编号 nn mm aia_i tt 分值
1 10\le10 5\le5 10\le10 55
2 500\le500 50\le50 20\le20 500\le500 77
3 5×103\le5\times10^3 200\le200 2000\le 2000 104\le10^4 1010
4 104\le10^4 10\le10 300\le300 105\le10^5 1515
5 2×105\le2\times10^5 200\le200 50\le50 107\le10^7 2525
6 5.2×105\le5.2\times 10^5 600\le600 10\le10 1015\le10^{15} 3838

输入数据保证同一个货架上,tt 升序。

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