Maximal Cow Pairings on a Number Line

Farmer John has arranged his N cows (1 ≤ N ≤ 5000) along a number line. Each cow is either a Holstein (denoted by H) or a Guernsey (denoted by G). The i^th cow is characterized by its breed (b_i \in {H, G}), its position (x_i) (with (0 \le x_i \le 10^9)), and its weight (y_i) (with (1 \le y_i \le 10^5)).

Following Farmer John’s signal, some cows form pairs subject to the following conditions:

(\bullet) Each pair must consist of one Holstein and one Guernsey whose positions differ by at most (K) ((1 \le K \le 10^9)); that is, if cow h (Holstein) and cow g (Guernsey) form a pair then [ |x_h - x_g| \le K. ]

(\bullet) Every cow is either paired with exactly one other cow or remains unpaired.

(\bullet) The pairing is maximal; in other words, there does not exist any two unpaired cows that could form a valid pair (i.e. an unpaired Holstein and an unpaired Guernsey whose positions differ by at most (K)).

Depending on the value of the parameter T, your task is to compute the possible range of the sum 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.

Any valid solution must output a number representing this sum. (Note that all formulas below are given in (\LaTeX) format.)

inputFormat

The first line contains three space‐separated integers: T, N, and K. \(T\) is either 1 or 2 as described above. \(N\) is the number of cows and \(K\) is the maximum allowed distance for a pair.

Each of the next N lines contains a description of a cow in the format:

xi bi yi

where \(x_i\) is the position, \(b_i\) is a character (either H or G) representing its breed, and \(y_i\) is its weight.

The cows may be given in an arbitrary order.

outputFormat

Output a single integer – the minimum (if T=1) or maximum (if T=2) possible sum of the weights of unpaired cows, over all maximal pairings.

sample

1 4 2
1 H 4
3 G 5
5 H 2
6 G 7

0

</p>