Ghép Đôi (Platinum)

Có $N$ con bò đứng trên một đường thẳng, mỗi con là giống Holstein (H) hoặc Guernsey (G). Mỗi con bò $i$ có:

• Giống: $b_i\in \{H,G\}$
• Vị trí: $x_i$ (các vị trí theo thứ tự tăng dần)
• Trọng số: $y_i$

Các con bò được ghép đôi theo các quy tắc sau:

• Mỗi cặp gồm đúng một con Holstein và một con Guernsey.
• Hai con bò được ghép chỉ khi khoảng cách giữa chúng không vượt quá $K$: $|x_h-x_g|\le K$.
• Mỗi con bò thuộc đúng một cặp hoặc không được ghép.
• Cách ghép phải là cực đại: không tồn tại hai con bò chưa được ghép (một Holstein và một Guernsey) mà khoảng cách giữa chúng $\le K$.

Cho biết loại bài toán $T$:

• Nếu $T=1$: Tìm tổng trọng số nhỏ nhất của các con bò không được ghép.
• Nếu $T=2$: Tìm tổng trọng số lớn nhất của các con bò không được ghép.

Dữ liệu vào

Dòng đầu tiên chứa ba số nguyên $T$, $N$, $K$.

• $N$ dòng tiếp theo, mỗi dòng chứa $b_i$, $x_i$, $y_i$ (theo thứ tự $x_i$ tăng dần nghiêm ngặt).

Dữ liệu ra

Một số nguyên duy nhất: tổng trọng số của các con bò không được ghép (nhỏ nhất nếu $T=1$, lớn nhất nếu $T=2$).

Ràng buộc

• $1\le N\le 5000$
• $1\le K\le {10}^9$
• $0\le x_i\le {10}^9$ (tăng dần nghiêm ngặt)
• $1\le y_i\le {10}^5$
• $T\in \{1,2\}$

Ví dụ

Ghi chú

• Trong ví dụ 1 (T=2): Nếu ghép G(1) với H(3) thì còn lại G(4), H(6), H(8) không ghép, tổng = 2+6+9=17, nhưng G(4) và H(6) cách nhau 2 ≤ 4, vi phạm tính cực đại. Do đó đây không phải cách ghép hợp lệ.
• Trong ví dụ 2 (T=1): Tổng trọng số tất cả bò = 22. Ghép tối ưu để tổng không ghép nhỏ nhất.