통학버스

직선 도로 위에 여러 아파트 단지가 있고, 같은 도로 위의 한 지점에 학교가 있다. 각 아파트 단지의 위치와 그 단지에 사는 학생 수가 주어진다.

통학버스는 한 대뿐이며, 매번 학교에서 출발해 아파트 단지의 학생들을 태운 뒤 다시 학교로 돌아온다. 버스는 정원 K명을 초과해 태울 수 없고, 모든 학생이 학교에 도착할 때까지 운행을 반복한다. 두 지점 사이의 거리는 두 좌표의 차의 절댓값이다.

학교의 위치, 아파트 단지들의 위치와 학생 수, 버스 정원이 주어질 때 모든 학생을 등교시키기 위해 필요한 통학버스 총 이동 거리의 최솟값을 구하라.

첫째 줄에 세 양의 정수 N, K, S가 공백으로 구분되어 주어진다.

• N은 아파트 단지의 수이며 2 <= N <= 30,000이다.
• K는 통학버스의 정원이며 1 <= K <= 2,000이다.
• S는 학교의 좌표이다.

다음 N개의 줄에는 아파트 단지의 좌표와 그 단지에 사는 학생 수가 공백으로 구분되어 주어진다. 학교와 모든 아파트 단지의 좌표는 0 이상 100,000 이하이고 서로 모두 다르다. 각 단지의 학생 수는 1 이상 2,000 이하이다.

모든 학생을 등교시키는 데 필요한 통학버스의 최소 총 이동 거리를 한 줄에 출력한다. 최소 이동 거리가 1,000,000,000을 초과하는 경우는 없다.