括价（brac）

题目描述

Y 同学有一个长度为 $n$ 的字符串 $s$ ，其中每个字符是 (、) 或 ?。

他要把每个 ? 替换成 ( 或 )。对于第 $i$ 个 ?：

请你求出使最终字符串成为合法括号序列的最小花费。若无法做到，输出 $-1$ 。

第一行包含一个整数 $n$ 。

第二行包含字符串 $s$ 。

接下来若干行，按 ? 在字符串中从左到右出现的顺序，每行包含两个整数 $a_i,b_i$ 。

输出一行一个整数，表示最小花费；若无解，输出 $-1$ 。

对于 $100\%$ 的数据，保证 $1 \le n \le 2\times 10^5$ ， $1\le a_i,b_i\le 10^9$ 。

测试点编号	分值	$n \le$	$a_i,b_i \le$	特殊性质
$1 \sim 2$	$10$	$20$	$100$	无
$3 \sim 5$	$15$	$2\times 10^5$	$10^9$	特殊性质 A
$6 \sim 8$	$15$	$2\times 10^5$		特殊性质 B
$9 \sim 12$	$20$	$5\times 10^4$		无
$13 \sim 16$		$2\times 10^5$		特殊性质 C
$17 \sim 20$		$2\times 10^5$		无