Hide

Problem K
Train Boarding

Punctual City is well known for the punctuality of its citizens and its public transportation system. It is particularly famous for its train system. It is always on time, and never too late (or even too early). Statistics about train boarding is regularly collected to keep things running smoothly.

A train has cars numbered $1$ to $N$ (from front to back), each of length $L$ meters. Each car has exactly one door for boarding located at the center ($L/2$ meters from each end of the car). There are no gaps between cars.

When the train stops at the boarding platform, each passenger waiting for the train walks to the door of the car which is closest to them, taking the higher numbered car in the case of a tie.

Given the location of the passengers relative to the train, help the city by reporting the longest distance that any passenger has to walk and the maximum number of passengers boarding any single car.

\includegraphics[width=0.9\textwidth ]{Diagram1.png}

Input

The first line of input contains three integers $N$ ($1 \leq N \leq 100$), which is the number of cars of the train, $L$ ($2 \leq L \leq 100$), which is the length of each car, and $P$ ($1 \leq P \leq 1\, 000$), which is the number of passengers waiting for the train. It is guaranteed that $L$ is an even number.

The next $P$ lines describe the location of the passengers relative to the train. Each line contains a single integer $x$ ($0 \leq x \leq 10\, 000$), which is the distance the passenger is behind the front-end of the train.

Output

Display the longest distance that any passenger has to walk on one line. On the next line, display the maximum number of passengers boarding any single car.

Sample Input 1 Sample Output 1
68 90 6
3809
288
2306
2215
4211
379
27
1
Sample Input 2 Sample Output 2
27 58 10
823
678
799
224
349
1002
308
978
602
265
28
1

Please log in to submit a solution to this problem

Log in