S사가 개발한 한 디펜스 게임은 국경 지대를 방어하는 게임이다. 이 게임에는 감시탑이라는 요소가 있다.

적이 오는지 감시하기 위해 국경 지대에 설치하는 감시탑은 국경 지대의 특정 위치에만 설치할 수 있다. 국경 지대는 일직선이라고 가정한다. 그리고 지형지물의 영향 탓에 설치할 수 있는 각 위치마다 감시탑의 설치 비용이 다르다. 여러분은 감시탑을 마음대로 설치할 수는 있지만, 설치 비용이 만만치 않기 때문에 최소의 비용으로 모든 국경 지대를 감시할 수 있도록 감시탑을 설치하려고 한다. 다만 국경 지대의 양 끝점에는 이미 감시탑이 설치되어 있다.

각 감시탑은 감시탑으로부터 거리 d인 곳까지만 감시할 수 있다. 국경 지대만 감시하면 되기 때문에 좌우로 d칸인 범위까지 감시할 수 있다고 생각하면 된다.

입력

• 첫 줄에 L,N,D가 주어진다.
  • L은 국경 지대의 길이이다. L은 10 이상 10^9 이하의 자연수이다.
  • N은 설치할 수 있는 감시탑의 개수를 의미한다. N은 100만 이하의 자연수이다.
  • D는 감시탑의 감시 범위이다. L 이하의 자연수이다.
• 다음 N줄에는 감시탑의 위치 x와 설치 비용 c가 주어진다. x에 대해 정렬되어 주어진다.
  • 위치 x는 국경 지대의 한쪽 끝에서부터의 거리를 의미하며, 0 이상 L 이하인 정수이다.
  • c는 10^9 이하의 자연수이다. c의 총합은 int의 범위를 넘지 않는다.

출력

가능한 경우 첫 줄에 모든 국경 지대를 감시할 수 있는 감시탑의 설치 비용의 최솟값과 설치한 감시탑의 개수를 출력한다.

입출력 예

입력

20 5 5
1 3
3 2
8 7
10 3
16 5

출력

3 1

입출력 보충

출처: sharifa