시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 216 130 121 59.024%

문제

N명이 서로 결제하겠다며 카드를 내밀고 있다. 사람들과 점원의 거리는 K이다. 처음으로 손을 K이상 뻗은 사람은 결제하게 되는 영예를 얻는다. 사람들은 다음과 같은 과정으로 손을 뻗는다. 1번 사람이 손을 A1,1만큼 뻗는다. → 2번 사람이 손을 A2,1만큼 뻗는다. → 3번 사람이 손을 A3,1만큼 뻗는다. → ...... → N번 사람이 손을 AN,1만큼 뻗는다. → 1번 사람이 손을 A1,2만큼 추가로 뻗는다. → 2번 사람이 손을 A2,2만큼 추가로 뻗는다. → ...... → N번 사람이 손을 AN,M만큼 추가로 뻗는다. 여기서 A는 2차원 배열의 형태로 입력으로 주어진다.

다시 말해, 1번부터 N번 사람까지 순서대로 손을 뻗는 것을 M번 반복하며, 각 순서에서 손을 뻗는 정도는 입력으로 주어진다.

이때, 가장 먼저 K이상 손을 뻗는 사람이 등장하는 순간 그 사람이 결제하며 상황이 종료된다. 항상 위 과정에서 손을 K이상 뻗는 사람이 존재하게 입력이 주어진다. 결제하게 되는 사람은 누구일까? 그리고 그 사람이 손을 뻗은 횟수는 몇 번일까?

입력

첫째 줄에 위에서 설명한 정수 NM(1 ≤ N, M ≤ 100), K(1 ≤ K ≤ 10,000,000)가 공백으로 구분되어 주어진다.

둘째 줄부터 N개의 각 줄에는 M개의 정수가 공백으로 구분되어 주어지며, 입력의 i+1번째 줄의 j번째 수는 Ai,j(1 ≤ Ai,j ≤ 10,000,000)를 의미한다.

출력

첫째 줄에 결제한 사람이 누구인지, 그 사람이 손을 뻗은 횟수는 몇 번인지를 의미하는 정수를 공백으로 구분하여 출력한다.

예제 입력 1

4 5 20
3 5 2 1 4
1 8 2 5 8
1 5 2 3 3
1 1 8 9 9

예제 출력 1

2 5

각 순서에서 어떤 사람의 손을 뻗은 정도는 아래와 같이 변한다.

1번 사람 : 3 → 2번 : 1 → 3번 : 1 → 4번 : 1 →

1번 : 8 → 2번 : 9 → 3번 : 6 → 4번 : 2 →

1번 : 10 → 2번 : 11 → 3번 : 8 → 4번 : 10 →

1번 : 11 → 2번 : 16 → 3번 : 11 → 4번 : 19 →

1번 : 15 → 2번 : 24

여기서 2번이 결제하게 되며 상황은 종료된다. 이때, 2번이 손을 뻗은 횟수는 5번이다.

예제 입력 2

2 5 100
1 1 1 1 1
50 50 50 50 50

예제 출력 2

2 2

2번 사람이 2번 만에 결제하게 된다. (여담으로, 1번 사람은 결제하고 싶지 않았던 것 같다.)

예제 입력 3

1 4 5
1 2 2 1

예제 출력 3

1 3