전구 수명 시험

전구에는 시간 단위의 수명이 표시되어 있지만, 이 값은 전구를 계속 켜 둔 것으로 가정한 값이다. 하지만 실제로는 전구를 껐다 켰다 하기 때문에, 실제 경과 시간 기준의 수명은 달라진다.

이를 측정하기 위해, 어떤 장치가 정해진 패턴에 따라 전구를 반복적으로 껐다 켰다 하고, 센서가 전구가 완전히 수명을 다하는 순간을 알려 준다. 패턴은 하나의 공백으로 구분된 원소들의 목록이며, 각 원소는 다음 중 하나이다.

• 양의 정수, 또는
• 반복 그룹: 괄호로 둘러싼 원소 목록 바로 뒤에 별표 *와 정수 $k$ ($1 \le k \le 1000000$)가 붙은 것으로, 괄호 안의 목록을 $k$번 반복한다는 뜻이다.

반복 그룹은 다른 반복 그룹 안에 중첩될 수 있다.

장치는 항상 전구를 켠 상태로 시작한 뒤, 패턴을 왼쪽에서 오른쪽으로 읽는다. 각 정수마다 그 수만큼의 시간 단위를 기다린 다음 전구의 상태를 토글한다(켜져 있으면 끄고, 꺼져 있으면 켠다). 패턴의 끝에 도달하면 다시 처음부터 시작하며, 이때 전구의 켜짐/꺼짐 상태는 초기화되지 않고 기다리는 시간의 순서만 반복된다.

예를 들어 패턴이 1 3 5라면, 장치는 전구를 켠 채로 시작한 뒤 1 단위를 기다리고 끄고, 3 단위를 기다리고 켜고, 5 단위를 기다리고 끄고, 1 단위를 기다리고 켜고, 3 단위를 기다리고 끄는 식으로 전구가 수명을 다할 때까지 진행한다.

패턴에는 반복 그룹이 포함될 수 있다. 패턴이 1 (3 5)*2 7이면 기다리는 시간의 순서는 1, 3, 5, 3, 5, 7, 다시 1, 3, 5, 3, 5, 7, … 이 된다. 즉, 그룹 3 5가 패턴을 한 번 지날 때마다 두 번 반복된다.

전구를 껐다 켜는 것 자체는 수명에 영향을 주지 않는다. 전구의 수명이 $n$ 시간이라는 것은 켜져 있던 시간이 누적으로 $n$ 시간이 되면 수명을 다한다는 뜻이다. $n$과 패턴이 주어졌을 때, 전구가 켜져 있던 시간의 합이 $n$ 시간이 될 때까지 실제로 몇 시간이 경과하는지 구하여라.

입력은 여러 개의 데이터 집합으로 이루어진다. 각 데이터 집합은 두 줄로 구성된다.

• 첫 번째 줄에는 전구의 수명을 나타내는 정수 $n$ ($1 \le n \le 1000000000$)이 주어진다.
• 두 번째 줄에는 위에서 설명한 형식의 패턴이 주어진다. 공백은 목록의 원소를 구분할 때만 나타나며 그 외의 위치에는 나타나지 않는다.

입력은 첫 번째 문자가 0인 줄(즉 $n = 0$인 데이터 집합)로 끝난다. 이 종료 줄에는 패턴 줄이 없으며 처리하지 않는다.

각 데이터 집합에 대해, 전구가 켜져 있던 시간의 합이 $n$ 시간이 될 때까지 경과하는 실제 시간을 나타내는 정수 하나를 한 줄에 출력한다.