They sent this programming problem by email...had to do it in at least 4 hours (measured the time I emailed the problem back to them): Best Route - Tyler Technologies Interview Programming Exercise Good Grain Delivery's truck has part of a tank of gas. They need to find a route from one city to another without running out of gas. Between each pair of cities are farmers ready to toss a sack of wheat into the truck bed, allowing the truck to accumulate a certain number of sacks each time it travels from one city to another. Some routes charge a grain toll, resulting in a negitive number of sacks gained. Road and grain information is represented as a series of tab-delimited lines like City1<tab>City2<tab>Distance<tab>Sacks indicating that traveling from City1 to City2 takes Distance miles and nets Sacks bags of grain. The input also lists trips Good Grain Delivery wants to make and the amount of miles they have left in the tank like this: Route?<tab>City1<tab>City2<tab>MaxDistance indicating a request (keyword "Route?") to calculate the most route from City1 to City2 of at most MaxDistance miles which maximizes the number of sacks of grain picked up. Blank lines in the input should be ignored. Write a program which can compute a route maximizing the number of grain sacks picked up. For each "Route?" line in the input, the output should contain a line (in the same order) of the format City1<tab>City2<tab>City3<tab>Distance<tab>Sacks indicating the route starts in City1, passes through City2, and ends in City3 covering a total of Distance miles and collecting Sacks bags of grain. All cities along the route should be listed, this example takes two steps. If it is not possible to reach the destination in the specified distance or less, the program should output Impossible:<tab>City1<tab>City2<tab>Distance Your program should read from standard input (stdin) and write to standard output (stdout). Sample input and output are available. If necessary, include any special instructions for compiling or running your program along with your submission or as a comment near the top of the file. You may use any programming language you like. Sample IN: Alicetown Bobville 10 50 Alicetown Carolina 30 60 Bobville Carolina 15 5 Carolina Bobville 15 5 Bobville Danburg 20 75 Danburg Bobville 20 40 Bobville Eveland 25 15 Carolina Danburg 10 20 Carolina Eveland 30 20 Danburg Eveland 40 40 Eveland Danburg 20 40 Eveland Frank City 15 -10 Frank City Danburg 10 35 Route? Alicetown Danburg 40 Route? Carolina Bobville 80 Route? Danburg Frank City 63 Route? Alicetown Frank City 40 Sample Out: Alicetown Bobville Danburg 30 125 Carolina Danburg Bobville Danburg Bobville 70 175 Danburg Bobville Eveland Frank City 60 45 Impossible: Alicetown Frank City 40