400452: GYM100186 D Test problem

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

D. Test problemtime limit per test2 secondsmemory limit per test256 megabytesinputinput.txtoutputoutput.txt

— Chris, I know that you don't have many people. This is because you hold on to these old education methods!

Several years ago, Simon showed up at the university with a super idea — put all the students on distance learning: "Teachers speak on a camera at home and students listen at their home!". He promised wholesale delivery of the equipment, waved sheets with diagrams around that showed how much money can the university make by renting out the freed lecture-halls and laboratories for offices. The classical university was on of the few, already at that time, that retained full-time education. Luckily, Simon was driven out. Soon "Association of classical and medical universities" appeared and most of the university's problems went away. Not that they disappeared completely, but those like Simon were not allowed even on the door step.

— So, Chris, I've got people. We've already took on more than a hundred graduates of the Academic university of information and communication technologies. But they all specialized on the "2038 problem" and we need to teach them a little bit more. Long story short, I need you, Chris, as a teacher of K ±  programming language. Here is the curriculum. The first group already waits for you, — Simon never thought that somebody could refuse such an offer.

Chris knew Simon too well. He flicked through the curriculum: yeah, in the classical university the teach that during the first course. Nothing complicated. Nevertheless, he didn't want to work with Simon very badly, but he still hoped that an open conflict can be avoided:

— You see, Simon, even the greatest curriculum has to be adopted for the audience. We need to test them first.

— Well, test then! Alice will guide you to the lecture-room.

Minutes later, Chris was dictating the problem to the group.

John received an interesting offer from his utility provider — pay for the services that were consumed during particular period of the day at a more favourable rates. Moreover, John can pick the time period of the cheaper rates himself. Provider only requests that the period starts and ends within one day and the duration of the period has to be the M'th portion of a day.

Utility provider uses a counting device which has a scale divided in N parts. That's why the beginning and the end of the chosen period have to be of integer value.

John decided to approach the problem seriously, so he was writing down the counter's readouts during D days every portion of the day (thus, he has D × N records). Now that he has enough data, he decided to choose M consequent portions of the day such that the summarized cost of the utility resources is the largest.

Your task is to determine the number of the first portion of the period chosen by the John and the amount of the resources which were consumed during D days considering only that period of the day.

Input

The first line contains integers D, N, M (2 ≤ D ≤ 1000, 2 ≤ N ≤ 1000, 1 ≤ M < N) — the number of days John wrote down the readouts, amount of points on the device scale and the number of portions when the provider offers discount rates.

The following D lines contain N non-negative integers each — readouts of the counters written down by John. All integers do not exceed 109.

Output

Output two integers in the first line — the order number of the portion of the day (counting from 1) from which the John's chosen segment of M portions starts and the amount of resources which were consumed during D days counting only consumption during this segment of each day.

If there exist several solutions, output any of them.

ExamplesInput
5 6 3
12 4 6 8 11 7
3 14 15 9 2 6
2 7 1 8 2 8
0 6 0 4 20 13
1 7 15 1 2 0
Output
2 105
Input
3 12 4
3 5 0 5 3 0 3 0 5 5 0 3
4 0 7 4 7 0 7 0 4 7 4 0
6 1 0 1 0 6 6 0 1 1 6 0
Output
4 42

加入题单

上一题 下一题 算法标签: