Устройство РубГолдберг
Люси необходимо сконструировать устройство преобразования энергии РубГолдберг. Возможные преобразования описываются в формате “INPUT OUTPUT TIME”, где INPUT и OUTPUT представляют собой входную и выходную энергии, TIME – время преобразования энергии в секундах. В наличии имеются четыре типа энергий: “CHEMICAL”, “ELECTRIC”, “MECHANICAL” и “THERMAL”.
Время работы устройства должно быть как можно ближе к target секундам. Устройство состоит из последовательных преобразований энергии, где результат очередного преобразования подается на вход следующего. Начинать свою работу устройство может с любого типа энергии, но в конце всех преобразований должна получиться энергия last.
Необходимо найти наименьшую возможную разность между target и временем работы построенного устройства.
Входные данные
Первая строка каждого теста содержит количество преобразований n (1 ≤ n ≤ 50), а также значения target и last (1 ≤ target, TIME ≤ 250000). Следующие n строк описывают преобразования энергии в формате “INPUT OUTPUT TIME”.
Выходные данные
Для каждого теста в отдельной строке вывести наименьшую возможную разность между target и временем работы построенного устройства.