1 import java.io.*;
    2 import java.util.*;
    3 
    4 public class solution1
    5   {
    6     static String pstring;
    7     static char[] pchars;
    8 
    9     static int findTokenEnd(int start)
   10     {
   11       while (start < pchars.length && !Character.isWhitespace(pchars[start]) && pchars[start] != ')')
   12         {
   13           start++;
   14         }
   15       return start;
   16     }
   17 
   18     static int findNextTokenStart(int start)
   19     {
   20       while (start < pchars.length && Character.isWhitespace(pchars[start]))
   21         {
   22           start++;
   23         }
   24       return start;
   25     }
   26 
   27     static int findClosingParantheses(int start)
   28     {
   29       int count = 1;
   30       for (; count > 0 && start < pchars.length; start++)
   31         {
   32           if (pchars[start] == '(')
   33             {
   34               count++;
   35             }
   36           else if (pchars[start] == ')')
   37             {
   38               count--;
   39               if (count == 0)
   40                 {
   41                   break;
   42                 }
   43             }
   44         }
   45       if (count > 0)
   46         {
   47           System.out.println("Input has unmatched parantheses.");
   48         }
   49       return start;
   50     }
   51 
   52     static void findTotalTimes(boolean odd_length, int mult, long times[], long totalTimes[])
   53     {
   54       if (odd_length)
   55         {
   56           totalTimes[0] = (mult/2)*(times[0]+times[1]) + (mult%2)*(times[0]);
   57           totalTimes[1] = (mult/2)*(times[0]+times[1]) + (mult%2)*(times[1]);
   58         }
   59       else
   60         {
   61           totalTimes[0] = times[0] * mult;
   62           totalTimes[1] = times[1] * mult;
   63         }
   64       return;
   65     }
   66 
   67     static int doBinarySearch(long left, boolean odd_length, int max_mult, long times[])
   68     {
   69       long[] recursiveTimes = {0,0};
   70       int lower = 0;
   71       int upper = max_mult;
   72       while (lower < upper - 1)
   73         {
   74           //System.out.println(lower + "\t" + upper);
   75           int med = (int)(((long)lower + (long)upper)/2);
   76           findTotalTimes(odd_length, med, times, recursiveTimes);
   77           if (recursiveTimes[0] < left)
   78             {
   79               lower = med;
   80             }
   81           else
   82             {
   83               upper = med;
   84             }
   85         }
   86 
   87       return lower;
   88     }
   89 
   90     static boolean computeTimeSpent(int start, int end, int mult, long left, boolean startState, long[] times)
   91     {
   92       //System.out.println("A:\t" + start + "\t" + end + "\t" + mult + "\t" + left + "\t" + startState);
   93       // Running counts
   94       times[0] = 0;
   95       times[1] = 0;
   96       boolean state = startState;
   97       int current = start;
   98 
   99       while (current < end)
  100         {
  101           //System.out.println(current);
  102           if (Character.isDigit(pchars[current]))
  103             {
  104               int tokenEnd = findTokenEnd(current);
  105               long time = Long.parseLong(pstring.substring(current, tokenEnd));
  106               if (state)
  107                 {
  108                   times[0] += time;
  109                   if (times[0] >= left)
  110                     {
  111                       times[0] = left;
  112                       break;
  113                     }
  114                 }
  115               else
  116                 {
  117                   times[1] += time;
  118                 }
  119               state = !state;
  120               current = findNextTokenStart(tokenEnd);
  121             }
  122           else if (pchars[current] == '(')
  123             {
  124               current++;
  125               int closing = findClosingParantheses(current);
  126               long recursiveTimes[] = {0, 0};
  127               boolean resulting_state;
  128               if (pchars[closing+1] == '*')
  129                 {
  130                   int mult_start = closing+2;
  131                   int mult_end = findTokenEnd(mult_start);
  132                   int multiplier = Integer.parseInt(pstring.substring(mult_start, mult_end));
  133                   resulting_state = computeTimeSpent(current, closing, multiplier, left-times[0], state, recursiveTimes);
  134                 }
  135               else
  136                 {
  137                   resulting_state = computeTimeSpent(current, closing, 1, left-times[0], state, recursiveTimes);
  138                 }
  139 
  140               //System.out.println("B:\t" + times[0] + "\t" + times[1] + "\t" + recursiveTimes[0] + "\t" + recursiveTimes[1] + "\t" + resulting_state);
  141 
  142               times[1] += recursiveTimes[1];
  143               times[0] += recursiveTimes[0];
  144               if (times[0] == left)
  145                 {
  146                   break;
  147                 }
  148               state = resulting_state;
  149               current = findNextTokenStart(findTokenEnd(closing+1));
  150             }
  151           else
  152             {
  153               current = end;
  154               System.out.println("incorrectly formatted data");
  155             }
  156         }
  157 
  158       boolean odd_length = (state != startState);
  159 
  160       if (times[0] == left)
  161         {
  162           // Not care
  163           return state;
  164         }
  165       else
  166         {
  167           if (mult > 1)
  168             {
  169               long[] recursiveTimes = {0,0};
  170               findTotalTimes(odd_length, mult, times, recursiveTimes);
  171               if (recursiveTimes[0] < left)
  172                 {
  173                   times[0] = recursiveTimes[0];
  174                   times[1] = recursiveTimes[1];
  175                   return startState ^ (odd_length && mult%2 == 1);
  176                 }
  177               else
  178                 {
  179                   int completed_reps = doBinarySearch(left, odd_length, mult, times);
  180                   long[] completedTimes = {0,0};
  181                   findTotalTimes(odd_length, completed_reps, times, completedTimes);
  182                   boolean intermediate_state = startState ^ (odd_length && completed_reps%2 == 1);
  183                   state = computeTimeSpent(start, end, 1, left-completedTimes[0], intermediate_state, recursiveTimes);
  184                   times[0] = completedTimes[0] + recursiveTimes[0];
  185                   times[1] = completedTimes[1] + recursiveTimes[1];
  186                   // Not care
  187                   return state;
  188                 }
  189             }
  190           else
  191             {
  192               // Not care
  193               return state;
  194             }
  195         }
  196     }
  197 
  198     public static void main(String[] args) throws IOException
  199       {
  200         BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
  201         while (true)
  202           {
  203             long limit = Long.parseLong(in.readLine().trim());
  204             if (limit == 0)
  205               {
  206                 break;
  207               }
  208 
  209             pstring = in.readLine().trim();
  210             pchars = pstring.toCharArray();
  211 
  212             long times[] = {0,0};
  213             boolean end_state = computeTimeSpent(0, pchars.length, 1, limit, true, times);
  214             //System.out.println("C:\t" + times[0] + "\t" + times[1] + "\t" + end_state);
  215 
  216             boolean odd_length = !end_state;
  217             if (times[0] < limit)
  218               {
  219                 int completed_reps = doBinarySearch(limit, odd_length, 2000000001, times);
  220                 long[] completedTimes = {0,0};
  221                 findTotalTimes(odd_length, completed_reps, times, completedTimes);
  222                 boolean intermediate_state = !(odd_length && completed_reps%2 == 1);
  223                 long[] recursiveTimes = {0,0};
  224                 computeTimeSpent(0, pchars.length, 1, limit-completedTimes[0], intermediate_state, recursiveTimes);
  225                 System.out.println(completedTimes[0] + recursiveTimes[0] + completedTimes[1] + recursiveTimes[1]);
  226               }
  227             else
  228               {
  229                 System.out.println(times[0] + times[1]);
  230               }
  231           }
  232       }
  233   }
  234