전구 수명

전구를 사면 포장지에 전구가 얼마나 오래 가는지 시간이 적혀 있습니다. 하지만 그 값은 전구를 계속 켜 둔다고 가정한 값입니다. 대부분의 사람은 전구를 껐다 켰다 하는데, 그러면 수명이 어떻게 달라질까요?

한 친구가 이를 측정하는 장치를 만들었습니다. 간단한 패턴을 주면 장치가 전구를 껐다 켰다 하고, 광센서가 전구가 끊어지는 순간을 감지합니다.

패턴 문법은 매우 단순합니다. 패턴은 공백으로 구분된 원소들의 목록이며, 각 원소는 다음 중 하나입니다.

• 밀리초 수를 나타내는 정수 $M$ ($1 \le M \le 1{,}000{,}000$), 또는
• 반복 목록: 하나 이상의 원소를 괄호로 감싼 뒤 *와 정수 $K$ ($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 \le N \le 1{,}000{,}000{,}000$)이 주어집니다. 둘째 줄에는 패턴 문자열이 주어지며, 길이는 최대 500자입니다.

패턴은 하나의 공백으로 구분된 원소들의 목록입니다. 각 원소는 정수 $M$ ($1 \le M \le 1{,}000{,}000$)이거나, 하나 이상의 원소를 괄호로 감싼 뒤 *와 정수 $K$ ($1 \le K \le 100$)를 붙인 반복 목록입니다. 공백은 목록의 원소를 구분할 때만 나타나고 그 밖의 위치에는 없습니다. 즉 * 앞뒤, 여는 괄호 바로 뒤, 닫는 괄호 바로 앞에는 공백이 없습니다. 반복을 모두 펼친 패턴 한 바퀴가 나타내는 전체 시간은 $1{,}000{,}000{,}000$ 이하입니다.

입력은 0 하나만 있는 줄로 끝납니다.

각 테스트 케이스마다, 전구가 $N$밀리초 동안 켜져 있게 될 때까지 흐른 전체 시간(밀리초)을 정수 하나로 한 줄에 출력하세요. 불필요한 공백을 넣지 말고, 답 사이에 빈 줄을 넣지 마세요.