Мобільний#2682

Мобільний

1 секунда

64 мегабайти

Дуже легка

Ви, напевно, бачили мобілі, що висять під стелями музеїв або аеропортів. У цій задачі ми зосередимося на мобілях, підвішених до стелі одним дротом, прикріпленим до точки опори на перекладині (яка також зроблена з дроту). На кожному кінці перекладини знаходиться або ще один дріт, що підвішує ще одну перекладину, або вантаж (зазвичай у вигляді якоїсь структури). Один із прикладів, створений Олександром Колдером, найвідомішим художником мобілів, показаний нижче.

Деякі мобілі прості, а деякі досить складні. Окрім художньої цінності, вони повинні бути врівноважені. Нагадаємо, що якщо відстань від точки опори до лівого кінця $d_{L}$ d_L, а до правого — $d_{R}$ d_R, то перекладина буде врівноважена, якщо добуток ваги на лівому кінці та $d_{L}$ d_L дорівнює добутку ваги на правому кінці та $d_{R}$ d_R. (Вага перекладин і дротів ігнорується.)

Наприклад, розглянемо мобіль, зображений нижче. Якщо вантаж $1$ становить $8$ одиниць, то ваги $2$ , $3$ , $4$ і $5$ мають бути $2$ , $6$ , $4$ та $4$ одиниць відповідно. Якщо вам відома структура мобіля (тобто розташування перекладин і точок опори) та значення однієї ваги, ви можете визначити всі інші ваги. Саме це і є вашим завданням — майже. Складність полягає в тому, що всі ваги мають бути цілими числами. Вам задано мінімальне значення однієї ваги, і потрібно підібрати всі інші так, щоб усі вони були цілими. Тобто задану мінімальну вагу може знадобитись трохи збільшити для досягнення цього.

Вхідні дані

Вхід для кожного тесту починається рядком із додатного цілого числа $n$ — кількості перекладин у мобілі. Перекладини пронумеровані від $1$ до $n$ . Наступні $n$ рядків описують перекладини у порядку їх номерів, у такому форматі:

$d_{L} d_{R} type_{L} type_{R} n_{L} n_{R}$ d_L\\ d_R\\ \text{type}_L\\ \text{type}_R\\ n_L\\ n_R

Тут $d_{L}$ d_L і $d_{R}$ d_R — цілі числа ( $\leq 20$ ), що задають відстані від точки опори до лівого та правого кінців перекладини; $type_{L}$ \text{type}_L та $type_{R}$ \text{type}_R — це або $W$ , або $A$ , де $W$ означає, що з відповідного кінця висить вантаж, а $A$ — що інша перекладина; $n_{L}$ n_L та $n_{R}$ n_R — індекси ваги або перекладини для лівого і правого кінця відповідно. Індекси ваг починаються з $1$ і йдуть підряд. Жодна перекладина не знаходиться нижче, ніж через $6$ елементів від верху мобіля. У наведеному вище прикладі найнижча перекладина знаходиться на відстані $3$ перекладин від верху.

Після опису перекладин наведено рядок вигляду $m w$ , що означає: вага $m$ має бути не менше $w$ , де $1 l e q w l e q 20$ 1 \\leq w \\leq 20.

Рядок, що містить $0$ , завершує вхідні дані.

Вихідні дані

Для кожного тесту виведіть один рядок, що містить мінімальну загальну вагу мобіля за умови, що вага $m$ не менше $w$ . Використовуйте формат, показаний у зразку виводу. Можна вважати, що всі значення вихідних даних будуть менше $1 0^{9}$ 10^9.

Приклади

Приклад 1