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