G. Path on Big Grid
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Consider a grid $$$c$$$ with $$$n$$$ rows and $$$m$$$ columns. The top-left corner of $$$c$$$ has coordinates $$$(0, 0)$$$, and the bottom-right corner has coordinates $$$(n-1, m-1)$$$.

The cell with coordinates $$$(i, j)$$$ of $$$c$$$ has cost $$$c_{i, j}$$$.

From $$$c$$$, create a big grid $$$C$$$ with $$$N\cdot n$$$ rows and $$$M\cdot m$$$ columns. The top-left corner of $$$C$$$ has coordinates $$$(0, 0)$$$, and the bottom-right corner has coordinates $$$(N\cdot n-1, M\cdot m-1)$$$.

The cell with coordinates $$$(i, j)$$$ of $$$C$$$ has cost $$$c_{\left \lfloor \frac{i}{N} \right \rfloor, \left \lfloor \frac{j}{M} \right\rfloor}$$$. $$$^{\text{∗}}$$$

A path through $$$C$$$ starts at $$$(0, 0)$$$, ends at $$$(Nn-1, Mm-1)$$$, and moves only right or down. The cost of the path is the sum of the costs of the cells visited.

What is the minimum cost of a path through the big grid $$$C$$$?

$$$^{\text{∗}}$$$$$$\lfloor x \rfloor$$$ is the floor function. It is the smallest integer that is less than or equal to $$$x$$$. For instance, $$$\lfloor 2.4 \rfloor = 2$$$, and $$$\lfloor 2 \rfloor = 2$$$

Input

The first line contains four integers, $$$n$$$, $$$m$$$, $$$N$$$, $$$M$$$. $$$(1 \leq n, m, N, M \leq 1000)$$$.

Then $$$n$$$ lines follow, each with $$$m$$$ numbers, $$$(1 \leq c_{i, j} \leq 1000)$$$ – the cost of the cells in $$$c$$$.

—

Tests in subtasks are numbered from $$$1−20$$$ with samples skipped. Each test is worth $$$\frac{100}{20}=5$$$ points.

Test $$$1-2$$$ satisfies $$$n = 1$$$ and $$$m = 1$$$.

Test $$$3-7$$$ satisfies $$$N = 1$$$ and $$$M = 1$$$.

Tests $$$8-20$$$ satisfy no additional constraints.

Output

One integer – the minimum cost of a path through the big grid $$$C$$$.

Example
Input
2 3 3 3
1 7 10
2 100 1
Output
41
Note

In the sample input, the costs of each cell in $$$c$$$ look as follows.

The costs of each cell in $$$C$$$ look as follows.

A path with minimal cost is indicated by the green cells below.

The cost is the sum of the costs of all cells in the path, which is $$$1 + 1 + 1 + 1 + 1 + 7 + 7 + 7 + 10 + 1 + 1 + 1 + 1 + 1 = 41$$$.

—

Problem Idea: Alex_C

Problem Preparation: Alex_C

Occurrences: Novice G