TAP2016I - Insect invasion

no tags 

[Due to SPOJ restrictions, this problem has been modified with respect to the original version used in the Argentinian Programming Tournament of 2016 in order to have multiple test cases per input file. The original version of this problem (in Spanish) can be found at http://torneoprogramacion.com.ar/wp-content/uploads/2016/09/tap2016.pdf ]

Ignacio liked to take part in programming competitions such as the Argentinian Programming Tournament during his years as a university student. He was very happy, and when he graduated he got a good job. However, with time routine and life in the big city started to make him feel uneasy. So one day he decided to move to the countryside and start a new life as a farmer. He hadn't saved a lot of money, but it was enough to buy a circular field.
His life as a farmer didn't have a good start, as tragedy came before being able to enjoy his first crop. In the middle of his field a scarecrow was in charge of keeping birds at bay, but for some strange reason it was connected to a radioactive gas pipe coming from a nuclear plant close by. One morning the pipe broke and the gas escaped, destroying most of his field. Ignacio couldn't do anything about it, so only a thin strip on the border of his field remained intact. But that was not all, as the few surviving plants were soon attacked by a swarm of mutant insects. This time Ignacio wouldn't stand still, so he decided to fight the insect invasion with trained frogs.
On the perimeter of his circular field he created $N$ ponds for the frogs, which he numberd from $1$ to $N$ in clockwise order. Then he bought $R$ frogs in a shop specializing in trained circus frogs, and numbered them from $1$ to $R$. During the night he put the frogs in the ponds, placing the $i$-th frog in pond number $B_i$. The frogs are very well trained, so at first light they will start to jump at a rate of one jump per minute. Each frog repeats a pattern of jumps every $K$ minutes. The $i$-th frog will jump advancing $A_{i,1}$ ponds in clockwise order during the first minute; it will then jump advancing $A_{i,2}$ ponds in the same direction, and so on until the $K$-th minute, in which it will jump advancing $A_{i,K}$ ponds. After that, the same pattern will be repeated, advancing $A_{i,1}$ ponds in the $K+1$-th minute, $A_{i,2}$ ponds in the $K+2$-th minute, etc. For example, let's consider the case with $N=5$ ponds and $K=3$. In this case, if frog number $1$ starts in pond $B_1 = 2$, being its jumping pattern $A_{1,1}=1$, $A_{1,2}=2$ and $A_{1,3}=1$, during its fist few jumps it will land in the ponds in the following order: $2$, $3$, $5$, $1$, $2$, $4$, $5$, $1$, $3$, $4$, $5$, \dots.
Ignacio is really quite unlucky, because the first frog suffers from an contagious disease which has turned it into a vegetarian. When the sun comes out and all the frogs start jumping, if a sick frog meets a healthy one in some pond, it will transmit it with this disease. In our example with $N = 5$ and $K = 3$ if there are $R = 2$ frogs and the second frog starts at pond $B_2 = 4$ with a jumping pattern given by $A_{2,1}=1$, $A_{2,2}=1$ and $A_{2,3}=1$, it will visit the ponds in the order 4, 5, 1, 2, 3, 4, $\ldots$. Therefore, the first frog will transmit its disease to the second one after $5$ minutes, when both meet at pond number $4$. Generically, more and more frogs will get infected until either all of them are sick, or the remaining healthy frogs never meet with the sick ones, reaching at that point the maximum number of infected frogs.
While writing this story the night has gone by, and even if Ignacio noticed that the first frog is sick, he is now unable to catch it because it is trained so well. He will have to go directly to the trained circus frog shop to complain. As he wants to ask for a refund, he should wait until the disease spreads completely, reaching the maximum number of infected frogs. Ignacio doesn't want to wait longer than necessary, so in order to help him you should answer two questions: What is the maximum number of infected frogs? In which minute will the last transmission of the sickness take pla

Ignacio liked to take part in programming competitions such as the Argentinian Programming Tournament during his years as a university student. He was very happy, and when he graduated he got a good job. However, with time routine and life in the big city started to make him feel uneasy. So one day he decided to move to the countryside and start a new life as a farmer. He hadn't saved a lot of money, but it was enough to buy a circular field.

His life as a farmer didn't have a good start, as tragedy came before being able to enjoy his first crop. In the middle of his field a scarecrow was in charge of keeping birds at bay, but for some strange reason it was connected to a radioactive gas pipe coming from a nuclear plant close by. One morning the pipe broke and the gas escaped, destroying most of his field. Ignacio couldn't do anything about it, so only a thin strip on the border of his field remained intact. But that was not all, as the few surviving plants were soon attacked by a swarm of mutant insects. This time Ignacio wouldn't stand still, so he decided to fight the insect invasion with trained frogs.

On the perimeter of his circular field he created N ponds for the frogs, which he numberd from 1 to N in clockwise order. Then he bought R frogs in a shop specializing in trained circus frogs, and numbered them from 1 to R. During the night he put the frogs in the ponds, placing the i-th frog in pond number Bi. The frogs are very well trained, so at first light they will start to jump at a rate of one jump per minute. Each frog repeats a pattern of jumps every K minutes. The i-th frog will jump advancing Ai,1 ponds in clockwise direction during the first minute; it will then jump advancing Ai,2ponds in the same direction, and so on until the K-th minute, in which it will jump advancing Ai,K ponds. After that, the same pattern will be repeated, advancing Ai,1 ponds in the K+1-th minute, Ai,2 ponds in the K+2-th minute, etc. For example, let's consider the case with N = 5 ponds and K = 3. In this case, if frog number 1 starts in pond B1 = 2, being its jumping pattern A1,1 = 1, A1,2 = 2 and A1,3 = 1, during its fist few jumps it will land in the ponds in the following order: 2, 3, 5, 1, 2, 4, 5, 1, 3, 4, 5, ...

Ignacio is really quite unlucky, because the first frog suffers from a contagious disease which has turned it into a vegetarian. When the sun comes out and all the frogs start jumping, if a sick frog meets a healthy one in some pond, it will transmit it this disease. In our example with N = 5 and K = 3 if there are R = 2 frogs and the second frog starts at pond B2 = 4 with a jumping pattern given by A2,1 = 1, A2,2 = 1 and A2,3 = 1, it will visit the ponds in the order 4, 5, 1, 2, 3, 4, ... . Therefore, the first frog will transmit its disease to the second one after 5 minutes, when both meet at pond number 4. Generically, more and more frogs will get infected until either all of them are sick, or the remaining healthy frogs never meet with the sick ones, reaching at that point the maximum number of infected frogs.

While writing this story the night has gone by, and even if Ignacio noticed that the first frog is sick, he is now unable to catch it because it is trained so well. He will have to go directly to the trained circus frog shop to complain. As he wants to ask for a refund, he should wait until the disease spreads completely, reaching the maximum number of infected frogs. Ignacio doesn't want to wait longer than necessary, so in order to help him you should answer two questions: What is the maximum number of infected frogs? In which minute will the last transmission of the sickness take place?

Input

There are multiple test cases in the input file. For each test case, the first line contains three integer numbers N, R and K. The integer N represents the number of ponds in the field (2 ≤ N  109), R represents the number of frogs ( R  200) and K represents the number of minutes after which the frogs repeat their jumping pattern ( K  200). The second line contains R integer numbers B1, B2, ..., BR, representing the i-th number the initial position of the i-th frog ( B_i  N for i = 1, ..., R, with Bi≠ Bj if  j). The following R lines describe the behavior of the frogs. The i-th of these lines contains K integer numbers Ai,1, Ai,2, ..., Ai,K, representing the number of ponds the i-th frog advances in each of its K jumps, in the order in which they occur ( Ai,j < N for i = 1, 2, ..., R and j = 1, 2, ..., K).

 

Output

For each test case, print a single line containig two integer numbers, representing the maximum number of infected frogs and the minute in which the last transmission of the disease takes place, respectively.

 

Example

Input:
5 2 3
2 4
1 2 1
1 1 1
1234 4 4
23 25 1000 67
20 4 26 222
18 28 1232 222
2 4 6 222
2 2 2 2
2 2 1
1 2
1
1

Output:
2 5
3 2
1 0


Added by:Fidel Schaposnik
Date:2016-09-21
Time limit:2s-5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU
Resource:Argentinian Programming Tournament 2016