Rube Goldberg Device#1558
Lucy must build a Rube Goldberg energy conversion device. Available energy conversions are described in the format "INPUT OUTPUT TIME", where INPUT and OUTPUT represent the input and output energy types, and TIME is the conversion time in seconds. There are four types of energy: "CHEMICAL", "ELECTRIC", "MECHANICAL", and "THERMAL".
The device's operating time must be as close as possible to target seconds. The device consists of a sequence of energy conversions, where the output of each conversion is used as the input for the next. The device can start with any type of energy, but must end with the energy type after all conversions.
You must find the minimum possible difference between target and the operating time of the constructed device.
The first line of each test case contains the number of conversions (1 \leq n \leq 50), and the values target and (1 \leq target,\, TIME \leq 250,\!000). The next lines describe the conversions in the format "INPUT OUTPUT TIME".
For each test case, print in a separate line the minimum possible difference between target and the operating time of the constructed device.
Example 1