By Gustavo Chermout, UNIFESO Brazil
Anne is a very applied student in the course of computer science. She doesn't like to be late, always try arrive 18:00 o'clock what is start time of classes. However the traffic in the city of Teresópolis between 16:30 and 19:00 is too slow, so a way that would normally take 10 minutes, it takes a much longer time. Anne leave her job at 17:00 and takes approximately X minutes to get to the point, however the buses toward the college pass exactly 17:30, at this time pass several buses with different ways that lead to college, if Anne miss it, she will have to wait until 17:50 to get another bus. From bus point what she generally wait, to college, easily take to more than 30 minutes if she doens't choose the bus that has the best way. Anne need to know what time she will get the college choosing the best route and arrive late.
Your task is, from N possible routes, say what time Anne arrive at college going for the best way, knowing she should get out of the varzea and reach the alto, with weights T time between a local and another, taking into consideration the transit (the T of varzea to the alto is not the same as the alto to varzea because the traffic in the opposite direction may be different) and report if whether or not delay. Assume that Anne always arrive at the point before 17:50 and you will always have a way between varzea and Alto.
The input contains several test cases. The first line contains three integers separated by a space, X (1 ≤ X ≤ 50), N (1 ≤ N ≤ 90) and V (1 ≤ V ≤ 10) indicating the time Anne take to go to the point of work, amount possible routes and the number of dots that it can move. The following are then N rows, each with two non-empty strings containing unique and local routes Anne can pass, and a separate integer by space, O, D and T (1 ≤ T ≤ 60), indicating that there is a route to get from place O to place The D and that this path will lead T minutes. The entrance ends when X = N = V = 0, and should not be processed.
Your program should produce two lines in the output. Containing the arrival time college and another containing "Ira se atrasar" (she will be late) or "Nao ira se atrasar" (she is not going to be late).
|Input Sample||Output Sample|
15 4 4