Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

D - LR

Problem Statement

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.

Input

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 ?. 

Output

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. 

Sample Input 1

R?????,2?)

Output for the Sample Input 1

29

Sample Input 2

???3??

Output for the Sample Input 2

999399

Sample Input 3

????,??,???

Output for the Sample Input 3

invalid

Sample Input 4

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

Output for the Sample Input 4

99

Sample Input 5

L(1111111111111111111111111111111111111111111,2)

Output for the Sample Input 5

1111111111111111111111111111111111111111111

Sample Input 6

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

Output for the Sample Input 6

199999999999999999999999999999999999999999999

Sample Input 7

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

Output for the Sample Input 7

0


Sample input:
R?????,2?)


Sample output:
29

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**13
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    s = S()
    l = len(s)
    fm = {}
    fm[''] = -1
    def f(s):
        if s in fm:
            return fm[s]
        l = len(s)
        r = -1
        if l > 5 and s[1] in '(?' and s[-1] in ')?':
            if s[0] in 'R?':
                for i in range(3,l-2):
                    if s[i] not in ',?':
                        continue
                    tl = f(s[2:i])
                    tr = f(s[i+1:-1])
                    if tl >= 0 and tr >= 0 and r < tr:
                        r = tr
            if s[0] in 'L?':
                for i in range(3,l-2):
                    if s[i] not in ',?':
                        continue
                    tl = f(s[2:i])
                    tr = f(s[i+1:-1])
                    if tl >= 0 and tr >= 0 and r < tl:
                        r = tl
        ff = True
        if s[0] == '0' and l > 1:
            ff = False
        for tc in 'RL,()':
            if tc in s:
                ff = False
                break
        if ff:
            r = int(s.replace('?', '9'))
        fm[s] = r
        return r

    r = f(s)
    if r < 0:
        return 'invalid'

    return r


print(main())