暂无测试数据。

春节到了，蒜头君要去拜年收红包了～

蒜头君需要经过一个 $n\times m$ 的危险地区，蒜头君需要从左上角 $(1,1)$ 进入危险地区，从右下角 $(n,m)$ 离开危险地区。除了左上角和右下角外，每个格子都有一只怪物，所有怪物的血量为 $h$，每只怪物可能有不同的攻击力，使用二维数组 $Atk[i][j]$ 表示攻击力（$1\leq i \leq n, 1\leq j \leq m$）。

为了保证安全，蒜头君邀请他的伙伴----魔法兔随行，魔法兔的基础攻击力为 $atk$。蒜头君和魔法兔每次只能向下或向右行走一格，当走到一个新的格子时，魔法兔和怪物会轮流进行攻击，魔法兔先手，那么攻击的顺序为：魔法兔 -> 怪物 -> 魔法兔 -> 怪物 -> ...，直到怪物死亡（生命值小于等于 $0$）。每次攻击，若攻击者的攻击力为 $atk$，则对手的生命值减少 $atk$。

魔法兔最多还可以释放 $num$ 次升级技能，使用技能后魔法兔接下来 $k$ 次移动，每次移动后会增加等同于移动到的格子的怪物的攻击力，$k$ 次移动后，攻击力恢复为初始攻击力。当然，魔法兔只能在技能结束后，才可以再一次释放技能。

请你帮蒜头君计算一下，到达终点时，魔法兔受到伤害的最小值。

输入格式

第一行，输入以空格隔开的六个正整数 $n,m,num,k,h,atk$。分别表示：

• 危险地区的大小为 $n\times m$；
• 魔法兔最多可以释放 $num$ 次技能；
• 每次技能持续移动 $k$ 次；
• 每只怪物的血量 $h$；
• 魔法兔的基础攻击力 $atk$。

接下来 $n$ 行，每行 $m$ 个数 $Atk[i][j]$，表示 $(i,j)$ 位置怪物的攻击力。

保证：$\bm{ n + m -1 \geq num\times k}$

输出格式

输出一个整数，表示魔法兔受到伤害的最小值。

数据范围

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

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

对于 $100\%$ 的测试数据，满足 $1 \le n,m \le 500,$ $1 \le num \le 10,$ $1 \le k \le 5,$ $1 \le atk \le h \le 100,$ $1 \le Atk[i][j] \le 100$，数据保证 $Atk[1][1] = Atk[n][m] = 0,\bm{ n + m -1 \geq num\times k}$。

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

3