Cutting a Log

A lumberjack wants to split a long log into several pieces so it can be loaded onto a truck.

The log has total length L. There are K given positions where the log may be cut, and each position is measured as a distance from the left end of the log. Cuts may be made only at those positions, and at most C cuts may be made. The same position may appear more than once, and the right endpoint L is not considered a cut that separates the log into pieces.

Choose cut positions so that the length of the longest resulting piece is as small as possible. Output that minimum possible longest length and, among all ways to achieve it, the smallest possible position of the first cut.

The first line contains three integers L, K, and C.

The second line contains K positions where the log may be cut.

Print two integers separated by a space on the first line.

The first integer is the minimum possible length of the longest piece. The second integer is the smallest possible first cut position among all ways to achieve that value.

• 2 <= L <= 1,000,000,000
• 1 <= K, C <= 10,000
• 1 <= cuttable position <= L