## USACO 2021 December Contest, Platinum

## Problem 2. Paired Up

Contest has ended.

**Log in to allow submissions in analysis mode**

At Farmer John's signal, some of the cows will form pairs such that

- Every pair consists of a Holstein $h$ and a Guernsey $g$ whose locations are within $K$ of each other ($1\le K\le 10^9$); that is, $|x_h-x_g|\le K$.
- Every cow is either part of a single pair or not part of a pair.
- The pairing is
*maximal;*that is, no two unpaired cows can form a pair.

It's up to you to determine the range of possible sums 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.

#### INPUT FORMAT (input arrives from the terminal / stdin):

The first input line contains $T$, $N$, and $K$.Following this are $N$ lines, the $i$-th of which contains $b_i,x_i,y_i$. It is guaranteed that $0\le x_1< x_2< \cdots< x_N\le 10^9$.

#### OUTPUT FORMAT (print output to the terminal / stdout):

The minimum or maximum possible sum of weights of the unpaired cows.#### SAMPLE INPUT:

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

#### SAMPLE OUTPUT:

16

Cows $2$ and $3$ can pair up because they are at distance $1$, which is at most $K = 4$. This pairing is maximal, because cow $1$, the only remaining Guernsey, is at distance $5$ from cow $4$ and distance $7$ from cow $5$, which are more than $K = 4$. The sum of weights of unpaired cows is $1 + 6 + 9 = 16$.

#### SAMPLE INPUT:

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

#### SAMPLE OUTPUT:

6

Cows $1$ and $2$ can pair up because they are at distance $2 \leq K = 4$, and cows $3$ and $5$ can pair up because they are at distance $4 \leq K = 4$. This pairing is maximal because only cow $4$ remains. The sum of weights of unpaired cows is the weight of the only unpaired cow, which is simply $6$.

#### SAMPLE INPUT:

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

#### SAMPLE OUTPUT:

1893

The answer to this example is $18+465+870+540=1893$.

#### SCORING:

- Test cases 4-7 satisfy $T=1$.
- Test cases 8-14 satisfy $T=2$ and $N\le 300$.
- Test cases 15-22 satisfy $T=2$.

****Note: the memory limit for this problem is 512MB, twice the default.****

Problem credits: Benjamin Qi