题目描述

wish 预备到大自然进行一次长期的旅游，他已经将想要参观游览的 n 个景点排成了一个列表（必须按照这个列表列出的顺序依次参观），他没有车，因此只能到旅行社旅游。他总计看中了 m 家旅行社，每家旅行社对于每个景点的收费都不相同，他希望能够在玩的尽兴的前提下花费的总金额最少（此乃人之常情嘛）。他可以选择任意一家旅行社开始游览第一个景点，他也可以在游玩了一个景点后离开当前的旅行社到其他的旅行社游玩下一个景点，不过在两个旅行队伍间的奔波是要花费路费的，幸亏这个路费很便宜，可以认为它是一个常数 w。

他对玩的尽兴的定义如下：每一家旅行社的服务各不相同，老是呆在一家旅行社自然无趣，因此他给出了一个常数 k，如果他在一家旅行社连续游玩的景点数达到了 k 个，那么他下一次就必须换一家旅行社，不然他会感到十分乏味。不过换过之后以后还可以再回到这家旅行社继续游览，此时可以再连续游玩 k 个景点。

数据规模

对于 30% 的数据，1 <= n, m <= 100，k = n。

对于 50% 的数据，1 <= n, m <= 1000，k = n。

对于 100% 的数据，1 <= n, m, k <= 1000，k <= n。

算法正确的前提下，保证中间结果不超过 longint 范围。

样例解释

第一个景点在第二家旅行社，第二个景点到第三家旅行社，第三个景点再回到第二家旅行社。

第一行四个正整数，n, m, k, w，含义已在题干中说明。

之后 m 行，每行 n 个正整数，其中第 i 行第 j 列的数 dij 表示第 i 个旅行社对第 j 个景点的收费为 dij。

一行一个数，表示你求出的最小花费。