시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB348768744418.838%

문제

벌목꾼 백은진은 나무를 종이 공장에 옮겨야 한다. 하지만, 통나무의 길이가 너무 길어서 트럭에 들어가지 않으므로, 여러개의 조각으로 나누려고 한다.

통나무의 길이는 L이고, K개의 위치에서만 자를 수 있다. 통나무를 자를 수 있는 위치가 주어진다. 이 위치는 통나무의 가장 왼쪽에서부터 떨어진 거리이다. 통나무를 자를 수 있는 횟수는 최대 C번이다.

통나무의 가장 긴 조각을 작게 만들고, 그 길이를 구해보자.

입력

첫째 줄에 세 정수 L, K, C가 주어진다. 둘째 줄에는 통나무를 자를 수 있는 위치가 주어진다.

출력

첫째 줄에 두 개의 수를 출력한다. 첫 번째 수는 가장 긴 조각의 길이이고, 두 번째 수는 그 때 처음 자르는 위치를 출력한다. 만약 가능한 것이 여러 가지라면, 처음 자르는 위치가 작은 것을 출력한다.

제한

  • 2 ≤ L ≤ 1,000,000,000
  • 1 ≤ K, C ≤ 10,000
  • 1 ≤ 자를 수 있는 위치 ≤ L

예제 입력 1

9 2 1
4 5

예제 출력 1

5 4

예제 입력 2

5 1 2
3

예제 출력 2

3 3

예제 입력 3

5 5 3
4 2 5 3 1

예제 출력 3

2 1

예제 입력 4

5 10 10
4 3 2 1 4 3 2 1 4 3

예제 출력 4

1 1

출처