蒜头君有一只坐骑，人马。

一天，蒜头君骑着他的坐骑走上了一片n×m的大荒野，一开始时，蒜头君在 (1,1) 点，他要前往(n,m) 点，蒜头君的人马每次可以向右或向下移动一格。然而这片荒野并不平静，除了起点和终点外每个点都有一只怪物会袭击蒜头君。

然而蒜头君的人马强大无比，它会先对怪物造成等同于它攻击力的伤害，然后蒜头君才会受到怪物的攻击，伤害等同于怪物的攻击力。然后人马再攻击怪物，怪物再攻击蒜头君，直至怪物死去，假设每个怪物具有相同的体力。

此外，蒜头君的人马还有一个强大无比的技能，使用该技能会使蒜头君接下来 k 次移动，每一次移动后增加等同于移动到的格子的怪物的攻击力，k 次移动后，人马攻击力恢复至初始攻击力。人马必须在当前一个技能释放完后才可以释放下一个技能，且一共可释放技能的次数有限，那么试问蒜头君从起点到终点最少受到多少点伤害。

注意：蒜头君的体力是无限的。

第一行六个正整数n,m,t,k,h,atk，表示地图长度、宽度、人马技能可使用次数、人马技能持续移动次数、每只怪物的体力和人马的初始攻击力。保证n+m−1≥t×k。

接下来 n 行，每行 m 个整数，表示每个点的怪物的攻击力。保证(1,1) 点、(n,m) 点为 0，其他点为正整数。

对于 30% 的测试数据，满足 1≤n,m≤10, 1≤t≤3,1≤k≤3；

对于 60% 的测试数据，满足1≤n,m≤100,1≤t≤10, 1≤k≤5；

对于 100% 的测试数据，满足1≤n,m≤500, 1≤t≤10, 1≤k≤5,1≤atk≤h≤100, 1≤ 怪物攻击力≤100。

输出一个整数，表示蒜头君受到的最小伤害。