#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

## Problem Description

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 x_{h} by y_{h} in size. Each grid square is marked with the flame intensity of that region of Hell.

Your ship occupies a rectangular space measuring x_{s} by y_{s} 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.

## Input

The first line of the input contains 4 space-separated integers: x_{h}, y_{h}, x_{s} and y_{s} (1 ≤ x_{s} ≤ x_{h} ≤ 1000 and 1 ≤ y_{s} ≤ y_{h} ≤ 1000).

The next y_{h} lines each contain x_{h} integers f_{ij} (1 ≤ f_{ij} ≤ 1000), each representing the flame intensity of Hellfire in that region.

## Output

The output should contain a single integer denoting the lowest coating strength required.

## Subtasks

Subtask 1 (5%): x_{s} = y_{s} = 1; 1 ≤ x_{h}, y_{h} ≤ 2

Subtask 2 (10%): x_{s} = y_{s} = 1; No restrictions on x_{h}, y_{h}

Subtask 3 (25%): 1 ≤ x_{s}, y_{s} ≤ 10; 1 ≤ x_{h}, y_{h} ≤ 100

Subtask 4 (60%): No restrictions

Subtask 5 (0%): Sample input

## Sample Input

4 3 2 1 2 1 3 4 4 3 1 3 1 3 2 1

## Sample Output

4

## Sample Output Explanation

The path of the red rectangle in the image below shows the best path that the ship can take.

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 5 | 10 | 1s | 64MB | Minimum |

2 | 10 | 10 | 1s | 64MB | Minimum |

3 | 25 | 10 | 1s | 64MB | Minimum |

4 | 60 | 5 | 1s | 64MB | Minimum |

5 | 0 | 1 | 1s | 64MB | Minimum |

### Judge Compile Command

g++-8 ans.cpp -o ship -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512