Treasures of the White Cobra
Gradually, before Mowgli, a cobra emerged, larger than any he had ever seen. This snake, nearly eight feet long, had turned as white as ivory from being in constant darkness. Even the round mark on its swollen neck had faded to a pale yellow. The cobra's eyes were red, like rubies, and the entire creature appeared both strange and wondrous.
This is what the white cobra said to Mowgli:
– I am the guardian of the royal treasure. Kurun Raja built a stone structure above me back when my skin was dark, and I could bring death to those who came here to steal. Through the stones, they lowered the treasure, and I heard the chants of the Brahmins, my masters.
The Brahmins constructed the vault in a rectangular shape NxM with square rooms. Upon entering the vault, you find yourself in one of these rooms, marked on the plan as S(sx,sy), and you can only exit to the light through the room F(fx,fy). You need to know a secret that will save you from certain death after encountering Tuu. In each room, there are Upanishads—ancient Indian treatises. The Upanishads primarily describe the impersonal aspect of the Absolute Truth and also specify how many coins can be taken from that room. In room S, you can take bags to store the gold. When passing through a room, you must place exactly the number of gold coins in the bag as indicated in the Upanishads—no more, no less. If you cannot fit the gold in the bag (because the bag is full), you must leave that bag. You can exit room F only with one bag, and there should be no empty bags taken from room S left behind. However, you may not be able to exit at all...
Input
The first line of the input file contains the numbers N and M (the dimensions of the vault), the 2-nd line contains the coordinates of room S, the 3-rd line contains the coordinates of room F, and the 4-th line contains the number K (the number of coins that fit in one bag). Following this are N rows of M numbers—instructions from the Upanishads, indicating how much gold can be taken from each corresponding room.
Constraints: 1 ≤ N ≤ 100, 1 ≤ M ≤ 100, 1 ≤ K ≤ 1000, all numbers from the Upanishads range from 1 to 1000.
Output
The output file should contain one number—the number of bags needed to be taken from room S to exit room F alive. If it is not possible to exit, output -1.