Paired Up

시간 제한2초메모리 제한1024 MB

요약

정렬된 소들의 위치와 무게가 주어질 때, 거리가 K 이내인 소들끼리 짝지어 최대로 짝을 이룰 때 남는 소들의 무게 합의 최솟값 또는 최댓값을 구한다.

난이도: 보통10점 중 7점
유형: 동적 계획법, 정렬
정답자: 아직 제출이 없습니다

문제

There are a total of $N$ ( $1\le N\le 10^5$ ) cows on the number line. The location of the $i$ -th cow is given by $x\_i$ ( $0 \leq x\_i \leq 10^9$ ), and the weight of the $i$ -th cow is given by $y\_i$ ( $1 \leq y\_i \leq 10^4$ ).

At Farmer John's signal, some of the cows will form pairs such that

Every pair consists of two distinct cows $a$ and $b$ whose locations are within $K$ of each other ( $1\le K\le 10^9$ ); that is, $|x\_a-x\_b|\le K$ .
Every cow is either part of a single pair or not part of a pair.
The pairing is maximal; that is, no two unpaired cows can form a pair.

It's up to you to determine the range of possible sums of weights of the unpaired cows. Specifically,

If $T=1$ , compute the minimum possible sum of weights of the unpaired cows.
If $T=2$ , compute the maximum possible sum of weights of the unpaired cows.

입력

The first line of input contains $T$ , $N$ , and $K$ .

In each of the following $N$ lines, the $i$ -th contains $x\_i$ and $y\_i$ . It is guaranteed that $0\le x\_1< x\_2< \cdots< x\_N\le 10^9$ .

출력

Please print out the minimum or maximum possible sum of weights of the unpaired cows.

예제3

예제 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

입력

예상 출력