Có tổng cộng \(N\) con bò (\(1\le N\le 10^5\)) trên trục số. Vị trí của con bò thứ \(i\) là \(x_i\) (\(0 \leq x_i \leq 10^9\)), và trọng lượng của con bò thứ \(i\) là \(y_i\) (\(1 \leq y_i \leq 10^4\)).

Theo hiệu lệnh của Farmer John, một số con bò sẽ ghép thành các cặp sao cho:

• Mỗi cặp gồm hai con bò phân biệt \(a\) và \(b\) có vị trí cách nhau không quá \(K\) (\(1\le K\le 10^9\)); tức là \(|x_a-x_b|\le K\).
• Mỗi con bò hoặc thuộc đúng một cặp, hoặc không thuộc cặp nào.
• Việc ghép cặp là cực đại; tức là không có hai con bò chưa ghép cặp nào có thể tạo thành một cặp.

Bạn cần xác định phạm vi các tổng trọng lượng có thể có của những con bò chưa ghép cặp. Cụ thể:

• Nếu \(T=1\), tính tổng trọng lượng nhỏ nhất có thể của các con bò chưa ghép cặp.
• Nếu \(T=2\), tính tổng trọng lượng lớn nhất có thể của các con bò chưa ghép cặp.

Dữ liệu vào

Dòng đầu tiên chứa \(T\), \(N\) và \(K\).

Trong mỗi dòng thuộc \(N\) dòng tiếp theo, dòng thứ \(i\) chứa \(x_i\) và \(y_i\). Đảm bảo rằng \(0\le x_1< x_2< \cdots< x_N\le 10^9\).

Dữ liệu ra

In ra tổng trọng lượng nhỏ nhất hoặc lớn nhất có thể của các con bò chưa ghép cặp.

Phân nhóm

• Dữ liệu 4–8: \(T=1\).
• Dữ liệu 9–14: \(T=2\) và \(N\le 5000\).
• Dữ liệu 15–20: \(T=2\).

Ví dụ

2 5 2
1 2
3 2
4 2
5 1
7 2

6

1 5 2
1 2
3 2
4 2
5 1
7 2

2

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

Nguồn

USACO 2021 December Contest, Gold — Paired Up. Tác giả: Benjamin Qi.

https://usaco.org/index.php?page=viewproblem2&cpid=1161