Paired Up

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Có $N$ con bò trên trục số, con thứ $i$ ở vị trí $x_{i}$ (đã sắp xếp tăng) với trọng số $y_{i}$ . Hai con bò có thể ghép cặp nếu khoảng cách giữa chúng không quá $K$ .

Một phép ghép cặp là tối đại nếu không tồn tại hai con bò chưa ghép có thể ghép với nhau.

Nếu $T = 1$ : Tìm tổng trọng số nhỏ nhất của các con bò chưa ghép trong phép ghép tối đại nào đó.
Nếu $T = 2$ : Tìm tổng trọng số lớn nhất của các con bò chưa ghép trong phép ghép tối đại nào đó.

Dữ liệu vào

Dòng $1$ : Ba số nguyên $T$ , $N$ , $K$ .
$N$ dòng tiếp: Mỗi dòng gồm hai số nguyên $x_{i}$ và $y_{i}$ .

Dữ liệu ra

In ra tổng trọng số theo yêu cầu.

Ràng buộc

$T \in {1, 2}$ .
$1 \leq N \leq 10^{5}$ .
$1 \leq K \leq 10^{9}$ .
$0 \leq x_{i} \leq 10^{9}$ (đã sắp xếp).
$1 \leq y_{i} \leq 10^{4}$ .

Ví dụ

Input	Output	Giải thích
2 5 2 1 2 3 2 4 2 5 1 7 2	6	Ghép cặp $(1, 3)$ và $(4, 5)$ . Bò $7$ không ghép. Hoặc ghép $(3, 4)$ , để $1, 5, 7$ chưa ghép với tổng $2 + 1 + 2 = 5$ . Tối đa là $6$ .

Bình luận

Không có bình luận tại thời điểm này.