Lightbulb Testing

Light bulbs advertise a lifetime in hours, but that rating assumes the bulb stays on continuously. In practice people switch bulbs on and off, which changes how long a bulb lasts in real time.

To measure this, a rig repeatedly switches a bulb on and off following a fixed pattern, and a sensor reports when the bulb burns out. A pattern is a list of elements separated by single spaces, where each element is either

• a positive integer, or
• a repeating group: a parenthesized list of elements immediately followed by an asterisk * and an integer $k$ ($1 \le k \le 1000000$), meaning the enclosed list is repeated $k$ times.

Repeating groups may be nested inside other repeating groups.

The machine always starts with the bulb on, then reads the pattern from left to right. For each integer it waits that many time units and then toggles the bulb (on becomes off, off becomes on). When it reaches the end of the pattern it starts over from the beginning; the bulb's on/off state is not reset, only the sequence of waits repeats.

For example, with the pattern 1 3 5 the machine starts with the bulb on, then: waits 1 unit and turns it off; waits 3 units and turns it on; waits 5 units and turns it off; waits 1 unit and turns it on; waits 3 units and turns it off; and so on until the bulb burns out.

A pattern may include repeating groups. For the pattern 1 (3 5)*2 7, the waits are 1, 3, 5, 3, 5, 7, then 1, 3, 5, 3, 5, 7, and so on: the group 3 5 is repeated twice on each pass through the pattern.

Switching the bulb on and off does not affect its life. A bulb has a life of $n$ hours, meaning it burns out after accumulating $n$ hours of on time. Given $n$ and a pattern, determine how many hours of real time elapse before the bulb has been on for a total of $n$ hours.

The input contains several data sets. Each data set consists of two lines:

• the first line is an integer $n$ ($1 \le n \le 1000000000$), the life of the bulb in hours;
• the second line is a pattern in the format described above. Spaces separate the elements of a list and appear nowhere else.

The input ends with a line whose first character is 0 (a data set with $n = 0$); this terminator has no pattern line and must not be processed.

For each data set, output a single integer on its own line: the number of hours of real time that elapse until the bulb has been on for a total of $n$ hours.