Có tổng cộng \(N\) con bò (\(1 \le N \le 5000\)) trên trục số, mỗi con thuộc giống Holstein hoặc Guernsey. Giống của con bò thứ \(i\) được cho bởi \(b_i \in \{H,G\}\), vị trí của nó được cho bởi \(x_i\) (\(0 \le x_i \le 10^9\)), và khối lượng của nó được cho bởi \(y_i\) (\(1 \le y_i \le 10^5\)).

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 một con Holstein \(h\) và một con Guernsey \(g\) có khoảng cách giữa hai vị trí không vượt quá \(K\) (\(1 \le K \le 10^9\)), tức là \(|x_h-x_g| \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.
• Cách ghép cặp là cực đại, tức là không có hai con bò chưa được ghé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 giá trị có thể có của tổng khối lượng những con bò không được ghép cặp. Cụ thể:

• Nếu \(T=1\), hãy tính tổng khối lượng nhỏ nhất có thể của những con bò không được ghép cặp.
• Nếu \(T=2\), hãy tính tổng khối lượng lớn nhất có thể của những con bò không được ghép cặp.

Dữ liệu vào

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

Với mỗi \(1 \le i \le N\), dòng thứ \(i\) trong \(N\) dòng tiếp theo chứa \(b_i,x_i,y_i\), tương ứng với con bò thứ \(i\). Dữ liệu bảo đảm \(0 \le x_1 < x_2 < \cdots < x_N \le 10^9\).

Dữ liệu ra

In ra tổng khối lượng nhỏ nhất hoặc lớn nhất có thể của những con bò không được ghép cặp, tùy theo giá trị của \(T\).

Phân nhóm

• Các test 4–7 thỏa mãn \(T=1\).
• Các test 8–14 thỏa mãn \(T=2\) và \(N \le 300\).
• Các test 15–22 thỏa mãn \(T=2\).

Lưu ý: Giới hạn bộ nhớ của bài này là 512 MB, gấp đôi giới hạn mặc định.

Ví dụ

2 5 4
G 1 1
H 3 4
G 4 2
H 6 6
H 8 9

16

1 5 4
G 1 1
H 3 4
G 4 2
H 6 6
H 8 9

6

2 10 76
H 1 18
H 18 465
H 25 278
H 30 291
H 36 202
G 45 96
G 60 375
G 93 941
G 96 870
G 98 540

1893

Nguồn

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

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