Howard has recently started a new full-time job which gives him ~K~ vacation days to use during the year. He is looking to spend all of his vacation days on a single trip to Hanoi, however he is having a hard time finding a pair of flights that are exactly ~K~ days apart.

Given the ~N~ flights to and from Hanoi this year, find the minimum cost of two flights ~A~ and ~B~ such that:

• ~A~ is a flight to Hanoi.
• ~B~ is a flight from Hanoi.
• ~A~ and ~B~ are exactly ~K~ days apart.

Input Specification

The first line of input contains two integers ~N, K~ ~(1 \le N \le 100~ ~000, 1 \le K \le 10^9)~, the number of flights and the number of vacation days that Howard has.

The next ~N~ lines each contain three terms ~D, T, C~ describing a flight, where:

• ~D~ ~(1 \le D \le 10^9)~ is the day the flight departs.
• ~T~ is either T or F, representing whether the flight is to or from Hanoi, respectively.
• ~C~ ~(1 \le C \le 10^9)~ is the cost of the flight.

Output Specification

Output the minimum cost of a pair of flights satisfying the conditions in the problem description, or -1 if no such pair exists.

Sample Input 1

2 3
1 F 1000
4 T 1000

Sample Output 1

-1

Sample Input 2

3 5
1 T 1000
3 T 100
6 F 1000

Sample Output 2

2000