I'll Pay, No I'll Pay

Interview

Time limit2sMemory limit512 MB

Summary

People take turns adding to their outstretched amount; find who first reaches the threshold K and on which of their turns.

Level: Easy2 of 10
Topics: Simulation, Implementation, Array
Solved: No attempts yet

Problem

N people are holding out their cards, each insisting on paying. The distance between the people and the clerk is K. The first person to reach out their hand by at least K earns the honor of paying. The people reach out their hands in the following process. Person 1 reaches out their hand by A1,1. → Person 2 reaches out their hand by A2,1. → Person 3 reaches out their hand by A3,1. → ...... → Person N reaches out their hand by AN,1. → Person 1 reaches out their hand by an additional A1,2. → Person 2 reaches out their hand by an additional A2,2. → ...... → Person N reaches out their hand by an additional AN,M. Here A is given as input in the form of a two-dimensional array.

In other words, the reaching out of hands in order from person 1 to person N is repeated M times, and the amount each person reaches out in each turn is given as input.

At the moment the first person to reach out by at least K appears, that person pays and the situation ends. The input is always given so that some person reaches out by at least K during the process above. Who ends up paying? And how many times did that person reach out their hand?

Input

The first line gives the integers N, M (1 ≤ N, M ≤ 100), and K (1 ≤ K ≤ 10,000,000) described above, separated by spaces.

From the second line, each of the N lines gives M integers separated by spaces, and the j-th number on the i+1-th line of the input means Ai,j (1 ≤ Ai,j ≤ 10,000,000).

Output

On the first line, print two integers separated by a space: who paid, and how many times that person reached out their hand.

Examples3

Example 1

Input

Expected output

2 5

Example 2
Input
```
2 5 100
1 1 1 1 1
50 50 50 50 50
```
Expected output
```
2 2
```
Example 3
Input
```
1 4 5
1 2 2 1
```
Expected output
```
1 3
```