#https://github.com/shakayami/ACL-for-python/blob/master/segtree.py class segtree(): n=1 size=1 log=2 d=[0] op=None e=10**15 def __init__(self,V,OP,E): self.n=len(V) self.op=OP self.e=E self.log=(self.n-1).bit_length() self.size=1<>i) def get(self,p): assert 0<=p and p>=1 r>>=1 return self.op(sml,smr) def all_prod(self): return self.d[1] def max_right(self,l,f): assert 0<=l and l<=self.n assert f(self.e) if l==self.n: return self.n l+=self.size sm=self.e while(1): while(l%2==0): l>>=1 if not(f(self.op(sm,self.d[l]))): while(l1 and (r%2)): r>>=1 if not(f(self.op(self.d[r],sm))): while(r r: z = 0 o = 1 else: z = -(r-l)//2 r,m = map(int,input().split()) t = s[:] + s[:] a = [1 if i == '(' else -1 for i in t] import itertools b = list(itertools.accumulate(a)) st = segtree(b,min,10**18) b.append(0) ans = 10**18 if o: for i in range(n): i#f o:break temp = (n - i) * r if i== 0: temp = 0 x = st.prod(i,i+n) x -= b[i-1] temp += c * m #print(i,x,z,t[i:i+n],temp,c) if x < 0: x *= -1 temp += ((x//2) + (x % 2)) * m*2 ans = min(ans,temp) #(()((()))) for i in range(n): if o:break temp = (n - i) * r if i== 0: temp = 0 x = st.prod(i,i+n) x -= b[i-1] x = b[n-1+i]-b[i-1] - x #print(i,x,z,t[i:i+n],temp,c) #x *= -1 y = x // 2 + (x % 2) #y = min(y,c) temp += y * m * 2 x -= 1 * y temp += c * m #print(temp) ans = min(ans,temp) print(ans)