As the Japanese imperial army looted Southeast Asia during the 1930s, Emperor Hirohito launched an organization called Kin no yuri, "Golden Lily", aimed at recovering and hiding the plunder, which consisted mainly of gold. A significant portion was hidden deep within caves in the Philippines such that it would remain safe and be used to finance Japan's military ambitions (Johnson, C. The Looting of Asia).
The war is now over and American intelligence agents have obtained the locations of the hiding spots. Beneath lies a massive amount of gold and treasure worth billions and since no one knows about it, could be used to finance a limitless number of causes.
Using advanced scanning technology, the exact location of the treasure has been found and is represented by a coordinate. In addition, the density for every unit of volume in the ground below has been determined and represents the average density of the material they will have to drill through, which can range from sediments and soil to solid rock.
Given the densities of the ground below as a 2-dimensional grid with the x-axis representing the ground and the y-axis representing the depth into the ground, determine the minimal amount of drilling that will be performed. Note that you start at the top-left corner and that you cannot drill upwards or diagonally; only to the left, right, or down.
The first line of input will consist of two integers, and , separated by a space representing the length (x-axis) and the depth (y-axis).
The next lines of input will contain space-separated integers. Each of these integers represents the density of the ground at that point.
The last line of input will consist of two integers each separated by a space representing the coordinate of the gold.
The only line of output should contain the minimal amount of drilling that will be required — that is, minimize the sum of the spaces travelled to reach the gold.
2 2 1 3 4 3 1 1
Explanation for Sample Output
The amount of drilling required to reach (0, 1) is 5 while to reach (1, 0) the value is 4. The gold is located adjacent to these two points, and since it has a density of 3, the output will be 7.