package main import . "fmt" func main() { var n int var s string Scan(&n, &s) a := make([]int, 2*n) for i := range a { Scan(&a[i]) } dp := make([][]int, 2*n+1) for i := range dp { dp[i] = make([]int, n+1) for j := range dp[i] { dp[i][j] = 1e18 } } dp[0][0] = 0 for i, c := range s { for j, x := range dp[i] { if c == '(' { if j+1 <= n { dp[i+1][j+1] = min(dp[i+1][j+1], x) } if j > 0 { dp[i+1][j-1] = min(dp[i+1][j-1], x+a[i]) } } else { if j+1 <= n { dp[i+1][j+1] = min(dp[i+1][j+1], x+a[i]) } if j > 0 { dp[i+1][j-1] = min(dp[i+1][j-1], x) } } } } Println(dp[2*n][0]) }