Trolleybuses of the same route pass through the stop every k (1<=k<=500) minutes. The arrival times of passengers at this stop are known. If a passenger arrives at a stop at the moment when a trolleybus arrives, then he has time to leave on it.
Write a program that determines what time the first trolleybus should go (this is a time from 0 to k-1) so that:
1) The total waiting time for a trolleybus for all passengers was minimal.
2) The maximum of the trolleybus waiting times was the minimum.
Input
The line contains the number k first, then the number N (0<=N<=100000). Then comes N numbers that specify the times of arrival of passengers
to stop. Each of these numbers is an integer from 0 to 100000.
Output
Write down two numbers that are the answers to the first and second questions of the problem, respectively.
If there are multiple solutions, print any of them.
Examples
| # |
Input |
Output |
| 1 |
100 5
0 210 99 551 99
|
10
51
|