Paired Up

문제

There are a total of $NN$ ($1\le N\le 50001\backslash le\; N\backslash le\; 5000$) cows on the number line, each of which is a Holstein or a Guernsey. The breed of the $ii$-th cow is given by $b_i\in \{H,G\}b\_i\backslash in\; \backslash \{H,G\backslash \}$, the location of the $ii$-th cow is given by $x_{i}x\_i$ ($0\le x_i\le {10}^{9}0\; \backslash leq\; x\_i\; \backslash leq\; 10^9$), and the weight of the $ii$-th cow is given by $y_{i}y\_i$ ($1\le y_i\le {10}^{5}1\; \backslash leq\; y\_i\; \backslash leq\; 10^5$).

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

• Every pair consists of a Holstein $hh$ and a Guernsey $gg$ whose locations are within $KK$ of each other ($1\le K\le {10}^{9}1\backslash le\; K\backslash le\; 10^9$); that is, $\mathrm{\mid }{x}_h-x_g\mathrm{\mid }\le K|x\_h-x\_g|\backslash 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=1T=1$, compute the minimum possible sum of weights of the unpaired cows.
• If $T=2T=2$, compute the maximum possible sum of weights of the unpaired cows.

입력

The first input line contains $TT$, $NN$, and $KK$.

Following this are $NN$ lines, the $ii$-th of which contains $b_i,x_i,y_{i}b\_i,x\_i,y\_i$. It is guaranteed that .

출력

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

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