임시 우편 접수대

문제

한 우체국은 마을의 우편물을 모으기 위해 하루 동안 임시 접수대 하나를 운영하려 한다. 마을의 길은 곧은 선분이며, 길의 왼쪽 끝 좌표는 0, 오른쪽 끝 좌표는 L이다. 접수대는 이 길 위에서 좌표가 정수인 곳에만 설치할 수 있다. 건물이 없는 좌표에도 설치할 수 있으며, 우편물을 보내는 장소와 같은 좌표에 설치해도 된다. 우편물을 보내는 장소는 N개다. i번째 장소의 좌표는 p_i이고, 그곳에서 보낼 우편물은 w_i개다. 서로 다른 장소가 같은 좌표에 있을 수 있으며, 이때도 각 장소의 우편물 수를 모두 계산한다. 모든 우편물은 해당 장소에서 접수대로 직접 운반한다. 좌표 p에서 좌표 x까지의 운반 거리는 |p-x|다. 접수대가 너무 멀면 주민이 이용하기 어렵다. 따라서 모든 장소에서 접수대까지의 거리가 R 이하여야 한다. 한 장소라도 거리가 R을 초과하면 그 좌표에는 접수대를 설치할 수 없다. 우편물의 개수가 적은 장소에도 같은 거리 제한을 적용하며, 거리의 합이 작다는 이유로 이 제한을 무시할 수는 없다. 접수대를 좌표 x에 설치했을 때의 전체 운반 비용은 각 장소의 우편물 수에 그 장소에서 접수대까지의 거리를 곱한 값을 모두 더한 것이다. 즉, 비용은 w_1|p_1-x|부터 w_N|p_N-x|까지의 합이다. 설치 비용이나 장소 사이를 이동하는 비용은 따로 없다. 거리 제한을 만족하는 정수 좌표 중 전체 운반 비용이 가장 작은 좌표를 찾으려 한다. 최소 비용을 만드는 좌표가 여러 개라면 가장 작은 좌표를 선택한다. 거리 제한을 만족하는 정수 좌표가 하나도 없을 수도 있다. 주어진 장소 정보로 선택할 접수대의 좌표와 전체 운반 비용을 구한다.

입력

첫째 줄에 정수 N, L, R이 공백으로 구분되어 주어진다. 1 ≤ N ≤ 100, 0 ≤ L ≤ 2,000, 0 ≤ R ≤ L이다.
다음 N개 줄의 i번째 줄에 정수 p_i와 w_i가 공백으로 구분되어 주어진다. 0 ≤ p_i ≤ L, 1 ≤ w_i ≤ 1,000이다. 같은 좌표가 여러 번 주어질 수 있다.

출력

설치할 수 있는 좌표가 있으면 선택한 좌표와 그때의 전체 운반 비용을 공백으로 구분하여 한 줄에 출력한다. 최소 비용인 좌표가 여러 개면 가장 작은 좌표를 출력한다. 설치할 수 있는 좌표가 없으면 -1만 출력한다.

3 6 4
0 2
3 1
6 2

3 12

2 5 2
0 3
5 1

-1

2 4 4
1 1
3 1

1 2

출처: Devin.KR 자체 제작