Traversing the flames of Hell is a formidable task, especially with your flimsy wooden vessel. Your first line of defence is a protective anti-fire coating, which, due to scarce supply, is difficult to attain.
Your assiduous cartographers have charted the fires of Hell, represented by a rectangular grid xh by yh in size. Each grid square is marked with the flame intensity of that region of Hell.
Your ship occupies a rectangular space measuring xs by ys grid squares. If at any instant the sum of flame intensities of the regions occupied by your ship is greater than the strength of your ship's protective coating, your ship would be consumed by the flames.
Given that your ship can only move horizontally or vertically along the gridlines of Hell, find the lowest coating strength required to get from the top-left corner to the bottom-right corner of the grid.
The first line of the input contains 4 space-separated integers: xh, yh, xs and ys (1 ≤ xs ≤ xh ≤ 1000 and 1 ≤ ys ≤ yh ≤ 1000).
The next yh lines each contain xh integers fij (1 ≤ fij ≤ 1000), each representing the flame intensity of Hellfire in that region.
The output should contain a single integer denoting the lowest coating strength required.
Subtask 1 (5%): xs = ys = 1; 1 ≤ xh, yh ≤ 2
Subtask 2 (10%): xs = ys = 1; No restrictions on xh, yh
Subtask 3 (25%): 1 ≤ xs, ys ≤ 10; 1 ≤ xh, yh ≤ 100
Subtask 4 (60%): No restrictions
Subtask 5 (0%): Sample input
4 3 2 1 2 1 3 4 4 3 1 3 1 3 2 1
The path of the red rectangle in the image below shows the best path that the ship can take.