Пристрій РубГолдберг
Люсі необхідно сконструювати пристрій перетворення енергії РубГолдберг. Можливі перетворення описуються у форматі "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 та часом роботи побудованого пристрою.