Мобильный
Вы, вероятно, видели мобильные конструкции, подвешенные к потолкам музеев или аэропортов. Мы сосредоточимся на типе, который подвешен к потолку на одном проводе, прикрепленном к точке поворота на рычаге (также сделанном из проволоки). На каждом конце рычага может быть либо другой провод, подвешивающий еще один рычаг, либо груз (обычно в виде какого-то дизайна). Ниже приведен пример, созданный Александром Колдером, самым известным художником мобильных конструкций.
Некоторые мобильные конструкции просты, а некоторые довольно сложны. Помимо художественной ценности, они должны быть сбалансированы. Помните, что рычаг будет сбалансирован, если произведение веса на левом конце и расстояния 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.