Bob and Alice’s Meet

Bob and Alice are quite closely friends. They are both intersted on Researching ciper. As everybody knows , they ,of course, are experienced computer users. So they always communicate their new reaserches on ciyper by Internet. But now, unfortunetly, their country is suffering from a cruel war caused by nucleus. However the enemy state is so powerful much more than their motherland. So after several months Bob and Alice's country is controled by enemy on many areas, including network. Any communications on the network are highly suspiciously. If anybody uncareful,he may lost his life! This situation is so dangerious to computer users. So Bob's mother and Alice's father make a decision together for their childern --- forbid them to use computer again. Bob and Alice can't disobey this dicesion ,but they also don't want to pause their new research. So they also make a decison together --- to meet at somewhere personally ,and , of coure,don't let their parents konw.

Now , Bob and Alice fasten the last chance on network communication to confirm the place they will meet at in the next days. The city they lived , has many roads and hotels. Of course, they can't talk just on the roads, and they also can't enter any buildings except hotels. So they decide to meet in a certain hotel in their city. As they know,the city's building pattern is very regular like a rectangle with many griddings in it. And all hotels and houses are built in lines and columns, so are roads. So they can only walk straightly by lines or columns. While it is a mountainly city, every buliding may has a different height above sea level.If you walk form a hotel with a height x at an initial speed v₀ to a hotel with a height y, then the speed on this road is surposed to be v₀ × 2^(x-y) . We already know that Bob lives in the city's left-up corner,and Alice lives in the right-down corner. The buliding in the grid among their houses are all hotels. and the length of the road between two neighbor( four directions connected) hotel is alway a same value L, and they set up at their own initial speed at the same time.

Now , they want to pick a path which will take them a fastest time to meet each other. Pitfully for them ,can you help them to commpute the minmum time to meet ? You should always remember that ,they only meet at a certain hotel ,so maybe one of them will reach a hotel and don't walk again to wait the other one to arrive.

There will be more than a test case. every case data goes like below:

Line 1 : Four space-separated integers: N, V_b, V_a, L.
N is the size of the rectangle of Bob and Alice's city. Va is Alice's initial speed, while V_b is Bob's initial speed. L is the length between two neighbor hotels .

Line 2 ~ Line N + 1 : every line has N space-separated integers,each one represents a hotel's height.

N = 0 indicates the end of input and should not be processed.

For each case , ouput an interger in a separated line which is the time they take to meet each other.The answer must round to three decimal places.

3 1 1 1
1 2 3
3 2 1
1 2 1
0 0 0 0

4.000

“网新恩普杯”杭州电子科技大学程序设计邀请赛