District Partitioning

A city is divided by n horizontal roads running from left to right and m vertical roads running from top to bottom. These roads split the city into (n+1)×(m+1) small districts, and the population of each small district is given.

Choose X horizontal roads and Y vertical roads as boundaries. Using only those chosen roads divides the city again into (X+1)×(Y+1) larger districts. The population of a larger district is the sum of the populations of the small districts contained in it.

Choose the roads so that the largest population among all larger districts is as small as possible. Output the chosen road numbers and that minimum possible maximum population.

The first line contains two integers n (1 ≤ n ≤ 20) and m (1 ≤ m ≤ 100). The second line contains two integers X (1 ≤ X ≤ n) and Y (1 ≤ Y ≤ m). Each of the next n+1 lines contains m+1 natural numbers. Each number is at most 10,000, and adjacent numbers are separated by one space.

On the first line, output the numbers of the X selected horizontal roads. On the second line, output the numbers of the Y selected vertical roads. On the third line, output the population of the most populated larger district after the partition.

Horizontal roads are numbered from 1 to n from top to bottom, and vertical roads are numbered from 1 to m from left to right. If there are several optimal answers, output any one of them. Put at least one space between numbers on the same line.