Мобільний
Ви, напевно, бачили мобілі, підвішені до стель музеїв або аеропортів. Ми розглянемо тип, підвішений до стелі одним дротом, який прикріплений до точки обертання на важелі (також зробленому з дроту). На кожному кінці важеля може бути або інший дріт, що підвішує ще один важіль, або вантаж (зазвичай у формі якогось дизайну). Нижче наведено приклад, створений Олександром Колдером, найвідомішим художником мобілів.
Деякі мобілі прості, а деякі досить складні. Окрім художньої цінності, ці мобілі повинні бути збалансовані. Згадайте, що якщо відстань d_L від точки обертання зліва і d_R справа, важіль буде збалансований, якщо добуток ваги на лівому кінці і d_L дорівнює добутку ваги на правому кінці і d_R. (Ми ігноруємо вагу важеля і дротів, що підвішують важелі.)
Наприклад, розгляньте мобіль, зображений нижче. Якщо вага 1 важить 8 одиниць, то ваги 2, 3, 4 і 5 повинні важити 2, 6, 4 і 4 одиниць відповідно. Насправді, якщо ви знаєте структуру мобіля, тобто розташування важелів і де знаходяться точки обертання на кожному важелі, і значення однієї ваги, ви можете визначити значення всіх ваг. Це ваша задача тут — майже. Здається, у вас є лише ваги, які мають цілі значення. Отже, вам буде задано бажане мінімальне значення однієї ваги, і ви повинні визначити значення інших ваг, щоб ці значення також були цілими. Таким чином, можливо, що задану мінімальну вагу потрібно трохи підвищити, щоб досягти цього.
Вхідні дані
Вхід для кожного тестового випадку починається з рядка, що містить додатне ціле число n, яке вказує кількість важелів у мобілі. Ці важелі пронумеровані від 1 до n. Наступні n рядків описують важелі, у порядку 1, 2, ..., n, і будуть у формі
d_L d_R type_L type_R n_L n_R
де d_L і d_R є цілими числами ≤ 20, що дають відстані від точки обертання до лівого і правого кінця важеля, type_L і type_R є або W, або A, вказуючи, що на лівому або правому кінці підвішено вагу або важіль, а n_L і n_R є індексними номерами ваги або важеля зліва і справа. Індекси для ваг починаються з 1 і є послідовними. Мобіль не матиме важеля, що підвішений далі, ніж 6 важелів від верху. У нашому прикладі вище найнижчий важіль знаходиться на відстані 3 важелів від верху.
Після опису важелів йде рядок у формі m w, що вказує, що вага m важить принаймні w, де 1 ≤ w ≤ 20.
Рядок, що містить 0, слідує за останнім тестовим випадком.
Вихідні дані
Для кожного тестового випадку виведіть один рядок, що дає мінімальну загальну вагу мобіля, якщо вага m є принаймні w. Використовуйте формат, наведений у зразку виводу. Ви можете припустити, що всі значення виводу будуть меншими за 10^9.