Пристрій Руба Голдберга#1558
Люсі має збудувати пристрій перетворення енергії типу Руба Голдберга. Доступні перетворення енергії описуються у форматі "INPUT OUTPUT TIME", де INPUT та OUTPUT — це типи вхідної та вихідної енергії, а TIME — час перетворення у секундах. Існує чотири типи енергії: "CHEMICAL", "ELECTRIC", "MECHANICAL" та "THERMAL".
Час роботи пристрою має бути якомога ближчим до target секунд. Пристрій складається з послідовності перетворень енергії, при цьому вихід кожного перетворення використовується як вхід для наступного. Пристрій може починати з будь-якого типу енергії, але після всіх перетворень має завершитися типом енергії .
Вам необхідно знайти мінімально можливу різницю між target і часом роботи зібраного пристрою.
Перший рядок кожного тесту містить число перетворень (1 \leq n \leq 50), а також значення target і (1 \leq target, TIME \leq 250{,}000). Наступні рядків описують перетворення у форматі "INPUT OUTPUT TIME".
Для кожного тесту в окремому рядку виведіть мінімально можливу різницю між target і часом роботи зібраного пристрою.
Приклад 1