Выгорание
Всякий раз, когда вы покупаете лампочку, на упаковке указывается время, в течение которого она должна прослужить. Однако это предполагает, что лампочка включена постоянно. Большинство людей включают и выключают свои лампочки. Как это влияет на их срок службы?
Ваш друг собрал установку для проверки этого. Простая схема будет включать и выключать лампочку, а датчик света сообщит, когда лампочка перегорит. Схема имеет очень простой синтаксис. Она состоит из списка элементов, разделенных пробелами. Каждый элемент — это либо число M (1 ≤ M ≤ 1,000,000), указывающее количество миллисекунд, либо повторяющийся список. Повторяющийся список состоит из одного или нескольких элементов, окруженных скобками, за которыми следует '*' и затем целое число K (1 ≤ K ≤ 100). Это число 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 ≤ 1,000,000,000), которое является ожидаемым сроком службы лампочки в миллисекундах.
Вторая строка будет содержать строку, которая является схемой. Схема не будет длиннее 500 символов. Схема состоит из списка элементов, разделенных одиночными пробелами. Каждый элемент — это либо число M (1 ≤ M ≤ 1,000,000), указывающее количество миллисекунд, либо повторяющийся список. Повторяющийся список состоит из одного или нескольких элементов, окруженных скобками, за которыми следует '*' и затем целое число K (1 ≤ K ≤ 100). Между элементами списка будут одиночные пробелы, но нигде больше. В частности, обратите внимание, что не будет пробелов вокруг '*' в конце повторяющегося списка, а также сразу после открывающей скобки или непосредственно перед закрывающей скобкой. Общее количество времени, представленное схемой, включая все повторения, не будет превышать 1,000,000,000.
Ввод заканчивается строкой, содержащей одну цифру 0.
Выходные данные
Для каждого тестового случая выведите одно целое число в отдельной строке, указывающее количество миллисекунд общего прошедшего времени до тех пор, пока лампочка не будет гореть в течение N миллисекунд. Не выводите лишние пробелы и не разделяйте ответы пустыми строками.