석유 채굴

회사 RectanGas는 예로부터 석유를 채굴해 왔고 이 분야에서 명실상부한 선두 기업이다. 마케터들은 이 회사의 성공을 오랫동안 자리를 지킨 최고경영자 덕분으로 본다. 그에 대해서는 조금 더 자세히 살펴볼 필요가 있다.

최고경영자는 학교에서 기하학을 전혀 배우지 않았고, 지금도 직사각형 말고는 다른 도형이 없다고 믿는다. 직사각형의 변이 좌표축과 평행하지 않을 수도 있다는 사실도 받아들이지 못한다. 그래서 모든 석유 시추탑은 다음과 같이 세워진다. 그는 지도에 네 점을 표시해 지도의 좌표축과 평행한 변을 가진 직사각형을 만들고, 그 점들에 대응하는 구역에 시추탑을 세우라고 지시한다. 시추탑은 짧은 시간 안에 해당 구역의 석유를 모두 채굴한다.

RectanGas는 2010년 5월 생산 계획을 거의 달성했다. 이제 정확히 $S$ 배럴만 더 채굴하면 된다. 그보다 많이 채굴하면 독점 혐의를 받게 되므로 안 된다. 적게 채굴하는 것도 안 된다. 시간을 엄수하는 최고경영자가 실망하면 직원 해고와 대규모 실업으로 이어지기 때문이다. 지질학자들이 지도를 자세히 조사해 구역별 석유 매장량을 확인했다. 이제 모든 조건을 만족하는 앞으로 세울 시추탑의 좌표를 구하는 프로그램을 작성해 달라.

첫 줄에는 세 정수 $n$, $m$, $S$가 주어진다. 이는 각각 지도의 세로와 가로 크기, 그리고 생산 목표이다 ($2 \le n, m \le 300$; $0 \le S \le 10^{7}$). 이어지는 $n$개의 줄에는 각각 $m$개의 정수 $a_{ij}$가 주어지며, 해당 구역의 석유 매장량을 나타낸다 ($0 \le a_{ij} \le 10^{6}$).

해고를 피할 수 없다면 $-1$을 출력한다. 그렇지 않으면 왼쪽 위 시추탑과 오른쪽 아래 시추탑의 좌표, 즉 네 수를 출력한다. 답이 여러 개라면 그중 아무거나 출력하면 된다.

첫 번째 예제의 그림이다.

모서리 시추탑의 값을 더하면 $1 + 5 + 2 + 8 = 16$이다.