Вигорання#3341

Вигорання

1 секунда

32 мегабайти

Легка

Кожного разу, коли ви купуєте лампочку, на упаковці вказано, скільки часу вона повинна прослужити. Це припущення базується на безперервному горінні лампочки. Проте більшість людей вмикають і вимикають свої лампочки. Як це впливає на їхній термін служби?

Ваш друг створив установку для тестування цього. Задано простий шаблон, його установка буде вмикати і вимикати лампочку, а світловий сенсор покаже, коли лампочка згорить. Шаблон має дуже простий синтаксис. Він складається зі списку елементів, розділених пробілами. Кожен елемент - це або число $M$ ( $1 \leq M \leq 1000000$ 1 \le M \le 1\,000\,000), що вказує кількість мілісекунд, або повторюваний список. Повторюваний список складається з одного або більше елементів, оточених дужками, і за якими слідує '*' та ціле число $K$ ( $1 \leq K \leq 100$ 1 \le K \le 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 \leq N \leq 1000000000$ 1 \le N \le 1\,000\,000\,000), яке є очікуваним терміном служби лампочки в мілісекундах.

Другий рядок міститиме рядок, який є шаблоном. Шаблон не буде довшим за $500$ символів. Шаблон складається зі списку елементів, розділених одиночними пробілами. Кожен елемент - це або число $M$ ( $1 \leq M \leq 1000000$ 1 \le M \le 1\,000\,000), що вказує кількість мілісекунд, або повторюваний список. Повторюваний список складається з одного або більше елементів, оточених дужками, і за якими слідує '*' та ціле число $K$ ( $1 \leq K \leq 100$ 1 \le K \le 100). Будуть одиночні пробіли, що розділяють елементи списку, але ніде більше. Зокрема, зверніть увагу, що не буде жодних пробілів навколо '*' в кінці повторюваного списку, ані одразу після відкриваючої дужки, ані безпосередньо перед закриваючою дужкою. Загальна кількість часу, представленого шаблоном, включаючи всі повторення, не перевищуватиме $1000000000$ 1\,000\,000\,000.

Вхідні дані завершуються рядком з одним $0$ .

Вихідні дані

Для кожного тестового випадку виведіть одне ціле число в окремому рядку, яке вказує кількість мілісекунд загального часу, що минув, поки лампочка горіла $N$ мілісекунд. Не виводьте зайвих пробілів і не розділяйте відповіді порожніми рядками.

Приклади

Приклад 1