There are a total of $N$ ($1≤N≤5000$) cows on the number line, each of which is a Holstein or a Guernsey. The breed of the $i$-th cow is given by $b_i∈{H,G}$, the location of the $i$-th cow is given by $x_i$ ($0≤x_i≤10^9$), and the weight of the $i$-th cow is given by $y_i$ ($1≤y_i≤10^5$).

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≤K≤10^9$); that is, $|x_h−x_g|≤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

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≤x_1 < x_2 < ⋯ < x_N ≤ 10^9$.

Output

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

Examples

Input 1

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

Output 1

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$.

Input 2

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

Output 2

6

Cows $1$ and $2$ can pair up because they are at distance $2≤K=4$, and cows $3$ and $5$ can pair up because they are at distance $4≤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$.

Input 3

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

Output 3

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≤300$.
• Test cases 15-22 satisfy $T=2$.

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

Problem credits: Benjamin Qi