구역 나누기

도시는 위에서 아래로 나란한 n개의 가로 도로와 왼쪽에서 오른쪽으로 나란한 m개의 세로 도로로 나뉘어 있다. 이 도로들은 도시를 (n+1)×(m+1)개의 작은 구역으로 나누며, 각 작은 구역에는 인구가 주어진다.

이 중 가로 도로 X개와 세로 도로 Y개를 경계선으로 선택한다. 선택한 도로만으로 도시를 다시 나누면 (X+1)×(Y+1)개의 큰 구역이 된다. 각 큰 구역의 인구는 그 안에 포함된 작은 구역들의 인구 합이다.

가장 인구가 많은 큰 구역의 인구가 가능한 한 작아지도록 도로를 선택하시오. 그때 선택한 도로의 번호와 최소 가능한 최댓값을 출력한다.

첫째 줄에 두 정수 n(1 ≤ n ≤ 20), m(1 ≤ m ≤ 100)이 주어진다. 둘째 줄에 두 정수 X(1 ≤ X ≤ n), Y(1 ≤ Y ≤ m)이 주어진다. 다음 n+1개의 줄에는 각 줄마다 m+1개의 자연수가 주어진다. 각 수는 10,000 이하이며, 공백 하나로 구분된다.

첫째 줄에 선택한 X개의 가로 도로 번호를 출력한다. 둘째 줄에 선택한 Y개의 세로 도로 번호를 출력한다. 셋째 줄에, 그렇게 나누었을 때 가장 인구가 많은 큰 구역의 인구를 출력한다.

가로 도로는 위에서 아래로 1부터 n까지, 세로 도로는 왼쪽에서 오른쪽으로 1부터 m까지 번호가 붙어 있다. 여러 최적해가 있으면 아무 것이나 출력해도 된다. 각 줄의 번호들 사이에는 하나 이상의 공백을 둔다.