시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB34141339.394%

문제

JAG Kingdom will hold a contest called ICPC (Interesting Contest for Producing Calculation).

At the contest, you are given a string composed of ?s and usable characters. You should replace all ?s in the string with the usable characters to make the string valid mathematical expression, before submitting it. The usable characters are L, R, (, ), ,, 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9.

For example, suppose that you are given the string "R(??3,??1?78??1?)?", then you can submit "R(123,L(1678,213))" as an example.

The submitted string will be scored as follows.

  • Let \(L\) and \(R\) be functions defined by \(L(x,y)=x\), \(R(x,y)=y\), where \(x\) and \(y\) are non-negative integers.

  • The submitted string will be regarded as a mathematical expression, whose value will be the score. For example, the score of the string "R(123,L(1678,213))" is \(R(123,L(1678,213)) = R(123,1678) = 1678\).

  • If the string cannot be evaluated as a mathematical expression about the functions \(L\) and \(R\), the string will be rejected. For example, "R", "R(3)", "R(3,2", "R(3,2,4)" and "LR(3,2)" are all invalid.

  • And strings that contain numbers with extra leading zeros, will be rejected. For example, "R(04,18)" is invalid, while "R(0,18)" is valid.

The winner of the contest will be the person getting the highest score. Your friend Jagger, who is going to join the contest, wants to be the winner. You are asked by Jagger to make the program finding the possible highest score for the input string.

입력

The input contains one string in a line, whose length \(N\) is between \(1\) and \(50\), inclusive.

You can assume that each element in the string is one of L, R, (, ), ,, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, or ?.

출력

Display the possible highest score in a line for the given string.

If it's impossible to get valid strings for the input string, print "invalid" in a line.

예제 입력 1

R?????,2?)

예제 출력 1

29

예제 입력 2

???3??

예제 출력 2

999399

예제 입력 3

????,??,???

예제 출력 3

invalid

예제 입력 4

?????,??,???

예제 출력 4

99

예제 입력 5

L(1111111111111111111111111111111111111111111,2)

예제 출력 5

1111111111111111111111111111111111111111111

예제 입력 6

L?1???????????????????????????????????????????????

예제 출력 6

199999999999999999999999999999999999999999999

예제 입력 7

L?0???????????????????????????????????????????????

예제 출력 7

0