문제
N 마리의 토끼가 일직선상에 서있다. i 번째 토끼는 xi 위치에 서있고, i 번째 토끼의 무게는 yi이다.
이 토끼들은 아래의 조건 하의 쌍을 이룬다.
- 모든 쌍은 두 마리의 다른 토끼 a와 b로 이루어져 있으며, 이들의 위치는 K만큼의 거리 안에 있다. 즉, |xa−xb|≤K 이다.
- 모든 토끼는 하나의 쌍의 일부이거나 쌍의 일부가 아니다.
- 가능한 최대한 쌍을 이룰 것이며, 쌍이 이루어지지 않은 토끼들은 쌍을 이룰 수 있다.
쌍을 이루지 못한 토끼들의 무게의 합의 범위를 구해야 한다.
T=1의 경우, 무게의 합의 최솟값을,
T=2의 경우, 무게의 합의 최댓값을 구하는 프로그램을 작성한다.
입력
첫 번째 줄에 T, N, K이 입력된다. (1≤T≤2, 1≤N≤105, 1≤K≤109)
두 번째 줄부터 N줄에 걸쳐 i번째 줄에 xi와 yi가 입력된다. (0≤x1<x2<⋯<xn≤109, 1≤yi≤104)
출력
입력에 맞춰 쌍을 이루지 못한 토끼들의 무게의 합의 최솟값 혹은 최댓값을 출력하시오.
예제1
입력
2 5 2
1 2
3 2
4 2
5 1
7 2
출력
6
예제2
입력
1 5 2
1 2
3 2
4 2
5 1
7 2
출력
2
예제3
입력
2 15 7
3 693
10 196
12 182
14 22
15 587
31 773
38 458
39 58
40 583
41 992
84 565
86 897
92 197
96 146
99 785
출력
2470
힌트
출처
USACO 2021 December Gold