3213. [SYOI 2019] oath sign

【题目描述】

在逃出空间后，CCCTATKKK被传送到了日♂暮♂里。

王♂的逝去。

van♂的入娱。

新日暮里的信♂仰正陷入崩坏。就在此时，那个自♂由的男人出现了。他change♂the♂boss♂this♂gym，用他的蕉♂驰♂蛋♂道赶到了这里，拯♂救日暮里。

NTZ ♂FA♂现了TAT后，集结了一帮弱♂子，想趁日♂暮♂里混乱之时对日♂暮♂里进行屠♂城（顺带除掉TAT）。

此时NTZ已经研♂FA♂出了抗体，为了打败NTZ，TAT需要肛♂助那个男人击♂败NTZ的弱♂子军队。

-----------------------------------------------------分鸽线-------------------------------------------------------

NTZ有M个军队，TAT获得了N支军队，TAT的每支军队由于获得了自♂由的气息，每一个NTZ的军队都可以由N支军队中的任何一支打♂败。但    

NTZ的军队必须严格按顺序击♂败。由于这N支军队的组成不同，它们打♂败每一个NTZ的军队所需时间也不同。T军i击♂败第j个N军的时间为T[i,j]。让另一支军队赶来接♂替当前军队战♂斗需要时间K（战♂斗过程中不可接替）。为了保证军队有足够的休♂息，每支军队最多只能连续击♂败NTZ的L个军队。也就是说，如果有一支军队连续击♂败了NTZ的L个军队，下一个军队就必须换一支军队来击♂败。TAT想知道，最短需要多长时间才能打♂败NTZ的军队呢？

【输入格式】

第一行有四个整数M, N, K, L

下面的N行，每行有M个整数。第I+1行的第J个整数为T[i,j]。

【输出格式】

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

【样例输入】

3 2 0 2



2 2 3



1 3 1

【样例输出】

4

【提示】

对于50%的数据，N<=5，L<=4，M<=10000

对于100%的数据，N<=5，L<=50000，M<=100000

【来源】

在此键入。