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.
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
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 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
Sample Input 2
3 5 1 T 1000 3 T 100 6 F 1000
Sample Output 2