ll@N;string@S;ll@A[2N],D[3N][2N],L=1d18,b;REP(j,N+1)D[0][j]=j?L:0;REP(i,2N)REP(j,N+1)b=S[i]>'(',D[i+1][j]=min(j?D[i][j-1]+b*A[i]:L,j<N?D[i][j+1]+!b*A[i]:L);wt(D[2N][0]);