题目描述

牛神有一只坐骑，人马。一天，牛神骑着他的坐骑走上了一片 $n\times m$ 的大荒野，一开始时，牛神在 $(1,1)$ 点，他要前往 $(n,m)$ 点，牛神的人马每次可以向右或向下移动一格。然而这片荒野并不平静，除了起点和终点外每个点都有一只怪物会袭击牛神。然而牛神的人马强大无比，它会先对怪物造成等同于它攻击力的伤害，然后牛神才会受到怪物的攻击，伤害等同于怪物的攻击力。然后人马再攻击怪物，怪物再攻击牛神，直至怪物死去，假设每个怪物具有相同的体力。此外，牛神的人马还有一个强大无比的技能，使用该技能会使牛神接下来 $k$ 次移动，每一次移动后增加等同于移动到的格子的怪物的攻击力，$k$ 次移动后，人马攻击力恢复至初始攻击力。人马的技能必须当前一个技能释放完后才可以释放下一个技能，且一共可释放技能的次数有限，那么试问牛神从起点到终点最少收到多少点伤害。

注意：牛神的体力是无限的。

输入格式

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

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

输出格式

输出一个整数，表示牛神受到的最小伤害。

4 3 2 1 7 4
0 2 4
3 5 1
2 3 2
5 4 0

3

子任务

对于 30% 的测试数据，满足 $1\le n,m \le 10,1\le t\le 3,1\le k\le 3$;

对于 60% 的测试数据，满足 $1\le n,m\le 100,1\le t\le 10, 1\le k\le 5$;

对于 100% 的测试数据，满足

$1\le n,m \le 500,1 \le t \le 10, 1 \le k \le 5, 1 \le atk\le h\le 100,1 \le 怪物攻击力 \le 100;$