Description

There are a total of $N$ cows on the number line, each ofwhich is a Holstein or a Guernsey. The breed of the $i$-th cow is given by $b_i\in \{{\tt H},{\tt G}\}$, the location of the $i$-th cow is given by $x_i$, and the weight of the $i$-th cow is given by $y_i$.

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 arewithin $K$ of each other; 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 apair.

It's up to you to determine the range of possible sums of weights of theunpaired cows. Specifically,

• If $T=1$, compute the minimum possible sum of weights of the unpairedcows.
• If $T=2$, compute the maximum possible sum of weights of theunpaired cows.

• $1\le N\le 5000$
• $1\le K\le 10^9$
• $0 \leq x_i \leq 10^9$
• $1 \leq y_i \leq 10^5$

Input Format

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 isguaranteed that $0\le x_1< x_2< \cdots< x_N\le 10^9$.

Output Format

The minimum or maximum possible sum of weights of the unpaired cows.

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

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

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 morethan $K = 4$. The sum of weights of unpaired cows is$1 + 6 + 9 = 16$.

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

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

Cows $1$ and $2$ can pair up because they are at distance $2 \leq K = 4$, andcows $3$ and $5$ can pair up because they are at distance $4 \leq K = 4$. Thispairing is maximal because only cow $4$ remains. The sum of weights ofunpaired cows is the weight of the only unpaired cow, which is simply $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

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

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 Credit

Problem credits: Benjamin Qi