## LCC '18 Contest 4 S3 - Flight Plan

View as PDF

Points: 7
Time limit: 2.0s
Memory limit: 64M

Author:
Problem types

Howard has recently started a new full-time job which gives him 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 days apart.

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

• is a flight to Hanoi.
• is a flight from Hanoi.
• and are exactly days apart.

#### Input Specification

The first line of input contains two integers , the number of flights and the number of vacation days that Howard has.

The next lines each contain three terms describing a flight, where:

• is the day the flight departs.
• is either T or F, representing whether the flight is to or from Hanoi, respectively.
• 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