Тестирование лампочки
Лампочки обычно указывают срок службы в часах, предполагая их непрерывное использование. Однако большинство людей включают и выключают лампочки, что может влиять на их срок службы. "Король Тыкв" хочет оценить лампочки различных производителей для светящихся красных глаз на новой игрушке "Экзорцист Барби". Для этого он поручил доктору Финкельштейну создать установку для тестирования.
Дана простая схема, которая включает и выключает лампочку, а датчик света фиксирует момент, когда лампочка перегорит. Схема имеет простой синтаксис и состоит из списка элементов, разделенных пробелами. Каждый элемент — это либо число, либо повторяющийся список. Повторяющийся список состоит из элементов, заключенных в скобки, за которыми следует звездочка '*' и целое число k (1 ≤ k ≤ 1000000).
Целое число k указывает, сколько раз список должен повториться. Машина Безумного Доктора всегда начинает с включения лампочки и проходит по схеме, ожидая указанное количество единиц времени для каждого числа, после чего переключает лампочку. Если лампочка включена, она выключается, и наоборот. Когда машина достигает конца схемы, она начинает снова с начала.
Например, для схемы:
1 3 5
Машина начнет с включения лампочки.
Она будет ждать 1 единицу времени и выключит лампочку.
Затем она будет ждать 3 единицы и включит лампочку.
Затем она будет ждать 5 единиц и выключит лампочку.
Затем она будет ждать 1 единицу и включит лампочку.
Затем она будет ждать 3 единицы и выключит лампочку.
Она будет продолжать так до тех пор, пока лампочка не перегорит.
Вот пример схемы с повторяющимся разделом:
1 (3 5)*2 7
Машина начнет с включения лампочки и будет менять её состояние после 1, затем 3, затем 5, затем снова 3, затем 5, затем 7, затем 1... Обратите внимание, что повторяющиеся разделы могут быть вложены друг в друга.
Доктор не силен в программировании, поэтому он попросил вас помочь. Он может легко измерить, сколько времени требуется, чтобы лампочка перегорела, но сколько времени это должно занять? Предположим, что включение и выключение лампочки НЕ влияет на её срок службы. Дано время жизни n в часах и схема включения и выключения лампочки, сколько часов пройдет, прежде чем лампочка будет гореть в течение n часов?
Входные данные
Входные данные содержат несколько наборов данных. Каждый набор данных состоит из двух строк. Первая строка содержит целое число n (1 ≤ n ≤ 1000000000), которое является сроком службы лампочки в часах. Следующая строка содержит схему, как указано выше. Элементы списка разделены пробелами, но нигде больше. Ввод заканчивается нулем в крайнем левом положении.
Выходные данные
Одно целое число, указывающее количество часов, прошедших до того, как лампочка будет гореть в течение n часов.