UOJ Logo Sharp Sword 剑锋 OI

SSOI

#579. 生产产品

统计

时间限制:1S / 空间限制:256MB

【问题描述】

  产品的生产需要M个步骤,每一个步骤都可以在N台机器中的任何一台完成,但生产的步骤必须严格按顺序执行。由于这N台机器的性能不同,它们完成每一个步骤的所需时间也不同。机器i完成第j个步骤的时间为T[i,j]。把半成品从一台机器上搬到另一台机器上也需要一定的时间K。同时,为了保证安全和产品的质量,每台机器最多只能连续完成产品的L个步骤。也就是说,如果有一台机器连续完成了产品的L个步骤,下一个步骤就必须换一台机器来完成。
  请计算最短需要多长时间。

【输入格式】

第一行有四个整数M, N, K, L;
接下来N行,每行有M个整数。第i+1行的第J个整数为T[j,i]。

【输出格式】

输出只有一行,表示需要的最短时间。

【输入样例1】

3 2 0 2
2 2 3
1 3 1

【输出样例1】

4

【数据范围】

对于50%的数据,N≤5,L≤4,M≤10000
对于100%的数据,N≤5, L≤50000,M≤100000

【题目来源】

Vijos1243