You are a guitar player and you are giving a concert tonight. Unfortunately, you are running a bit late, and you still need to travel across town to get to the concert hall. You will drive as fast as possible (above the speed limit) and you are willing to drive through red lights at the risk of getting fined. However, you do not want to arrive early because you don't like the artist playing before you. Your goal is to get to the concert hall exactly on time.
The city is a rectangular grid of squares described by the String cityMap. The j-th character of the i-th element of cityMap is the square at row i, column j. Each square is one of the following:
- X: A house. You cannot enter this square.
- .: A safe road. You can drive here safely without ever getting a speeding ticket.
- Y: Your starting location. After time = 0, this becomes a safe road.
- C: The concert hall. As soon as you enter this square, you are at your final destination and you cannot leave.
- T: A traffic light. See below for details.
- S: A speed trap. You will get fined speedingTicket dollars every time you enter a square containing a speed trap.
You are given an int timeLeft, the number of seconds you have left until your concert starts. At time 0, you are at your starting location. At the speed you are driving, it takes you exactly one second to move to any of the 4 adjacent squares. At each second, you must move to an adjacent square unless you are at a traffic light. You are never allowed to directly go back to the immediately previous square of your path. If you are currently at a traffic light, you have two options: make a move during the upcoming second (like you would from any other square), or stay at the traffic light for exactly one second before making your next move. If you stay at the traffic light for one second, you are guaranteed to not get fined. Otherwise, you have a 70% chance of getting fined redLight dollars.
Determine the route that will take you to the concert hall in exactly timeLeft seconds. If there are multiple such routes, choose the one that minimizes your total expected fine. Return your total expected fine, or -1 if there is no way to get to the concert hall exactly on time.