Minimum Army Deployment

A country A is represented by an $$M\times N$$ grid. Each cell is either a town or a mountainous region (which is uninhabited). lanzerb divides his tribe into several armies with the following rules:

• Each army can start from any town.
• An army can only move downward (i.e. to rows with a larger index) and cannot move upward.
• On its journey, an army can only travel through towns and cannot go through mountains.
• If a town has been visited by one army, it cannot be visited by any other army.
• An army may stop at any town.

Unlike the chess knight which moves in a 1×2 pattern, each army can only move exactly in a $$R\times C$$ manner. That is, if an army is at cell (i, j), then it can only move to either (i+R, j+C) or (i+R, j-C) provided that the target cell exists and is a town.

Assume that whenever an army passes through a town it occupies it, your task is to determine the minimum number of armies required to cover (occupy) all the towns in the grid.

Hint: This is equivalent to covering all vertices of a directed acyclic graph (DAG) with vertex-disjoint paths, where each town is a vertex and a directed edge exists from town u to town v if an army can move from u to v. It is known that the minimum path cover in a DAG equals \(n - \text{maximum matching}\) in an appropriately constructed bipartite graph.

inputFormat

The first line contains four integers M, N, R, and C where the grid has M rows and N columns and the allowed move is a jump of R rows and C columns.

The next M lines each contain N integers. Each integer is either 1 or 0. A value of 1 indicates a town while 0 indicates a mountainous region.

You may assume that 1 ≤ M, N ≤ 1000 and 1 ≤ R, C ≤ M, N respectively.

outputFormat

Output a single integer representing the minimum number of armies required to cover all the towns.

sample

3 3 1 2
1 1 1
1 0 1
1 1 1

4