Люси необходимо сконструировать устройство преобразования энергии РубГолдберг. Возможные преобразования описываются в формате “**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 и временем работы построенного устройства.