Problem D: PIPI打dota

Problem D: PIPI打dota

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 530  Solved: 112
[Submit] [Status] [Web Board] [Creator:]

Description

PIPI是个dota迷,最近喜欢上了敌法师这个英雄。

blink是敌法师的一个技能,敌法师可以使用blink完成瞬间移动。

刀塔的世界是一个n × m 的矩阵(n行m列)。

敌法师的blink技能的瞬移距离为d,冷却时间为c。每当敌法师使用blink时,他可以从(x,y)移动至(x+d,y),(x-d,y),(x,y+d)和(x,y-d)4个位置之一,并且不花费任何时间,但是要等c秒之后才能再次使用blink。初始时,敌法师的blink处于可用状态。

敌法师本身具有移动能力,他能花费1秒的时间从(x,y)移动至(x+1,y),(x-1,y),(x,y+1)和(x,y-1)4个位置之一。敌法师也可以选择保持原地不动,但是依旧需要花费1秒。

刀塔的世界会定时刷新出一种叫做赏金神符(Bounty Rune)的东西,抢到它,敌法师就能获得不少的金钱。

现在敌法师得到消息,在(txty)处刷新出了一个赏金神符。此时的敌法师位于(sx,sy),打算尽全力赶过去抢符。敌法师非常熟悉他所在的世界,所以他能用最快的速度赶到赏金神符刷新的地方,但是他不会算数,不知道他一共要花多少的时间。而你虽然不熟悉刀塔世界,但你的算数能力非常好。所以,你能算出他最少要花多少时间才能到达目的地吗?

Input

输入的第一行为n,m,d和c(2<=n,m<=500,1<=d,c<=12 且 d<=min(n,m))。

第二行为txty

第三行为sxsy

保证敌法师的初始位置和赏金神符的刷新点都在刀塔世界里。

Output

输出一行,内容为1个数字,表示敌法师移动到赏金神符的刷新点最少要花多少时间(单位:秒)。

Sample Input

3 3 1 1
1 1
3 3

Sample Output

2