Burnout

Whenever you buy a light bulb, its package states how long the bulb should last. But that rating assumes the bulb stays on continuously. Most people switch their bulbs on and off, so how does that change the lifetime?

A friend has built a rig to measure this. Given a simple pattern, the rig turns the bulb on and off while a light sensor detects when the bulb burns out.

The pattern uses a very simple syntax. It is a list of elements separated by spaces. Each element is one of:

• a number $M$ ($1 \le M \le 1{,}000{,}000$) giving a number of milliseconds, or
• a repeating list: one or more elements enclosed in parentheses, followed by * and an integer $K$ ($1 \le K \le 100$) telling how many times the parenthesized list repeats.

The rig always starts with the bulb on and then walks through the pattern. For each number it waits that many milliseconds and then switches the bulb: if the bulb is on it is turned off, and if it is off it is turned back on. When it reaches the end of the pattern, it starts over from the beginning.

For example, with the pattern:

1 3 5

the rig starts by turning the bulb on, then:

• waits 1 millisecond and turns the bulb off,
• waits 3 milliseconds and turns the bulb on,
• waits 5 milliseconds and turns the bulb off,
• waits 1 millisecond and turns the bulb on,
• waits 3 milliseconds and turns the bulb off,

and continues like this until the bulb burns out.

Here is a pattern with a repeating section:

1 (3 5)*2 7

the rig changes the bulb's state after 1 millisecond, then 3, then 5, then 3, then 5, then 7, then 1, and so on. Repeating sections may be nested inside other repeating sections.

Assume that switching the bulb on and off does not affect its life, and that switching takes no time.

Given a life $N$ in milliseconds and a switching pattern, determine how many milliseconds of actual elapsed time pass before the bulb has been on for exactly $N$ milliseconds in total.

The input contains several test cases. Each test case consists of two lines. The first line contains an integer $N$ ($1 \le N \le 1{,}000{,}000{,}000$), the expected life of the bulb in milliseconds. The second line contains the pattern string, which is at most 500 characters long.

The pattern is a list of elements separated by single spaces. Each element is either a number $M$ ($1 \le M \le 1{,}000{,}000$) or a repeating list: one or more elements in parentheses followed by * and an integer $K$ ($1 \le K \le 100$). Single spaces separate elements of a list and appear nowhere else — there is no space around the *, none immediately after an opening parenthesis, and none immediately before a closing parenthesis. The total amount of time represented by one full pass of the pattern, including all repetition, is at most $1{,}000{,}000{,}000$.

The input terminates with a line containing a single 0.

For each test case, output a single integer on its own line: the total elapsed time in milliseconds until the bulb has been on for $N$ milliseconds. Output no extra spaces, and do not separate answers with blank lines.