定义一个只包括 ( 和 ) 的字符串 $s$ 为括号串，定义合法括号串如下：

• 空串是合法括号字符串
• 如果 $A$ 和 $B$ 都是合法括号串，那么 $A+B$ 也是合法括号串
• 人如果 $A$ 是合法括号串，那么 $(A)$ 也是合法括号串

给出一个长度为 $2n$ 的括号序列 $s$，修改第 $i$ 个括号有代价 $a_i$，$q$ 次修改 $a_i$ 并询问将 $s$ 修改为合法括号串的最小代价和，修改是永久的，询问相互独立。

输入格式

第一行两个正整数 $n,q$。

接下来一行 $2n$ 个非负整数 $a_1,\ldots,a_{2n}$。

接下来一行一个长为 $2n$ 的括号串 $s$。

接下来 $q$ 行，每行两个非负整数 $i,x$，表示将 $a_i$ 修改为 $x$。

输出格式

输出 $q+1$ 行，顺序表示初始和进行完每次修改后的答案。

样例

样例输入 1

3 5
9 2 2 2 2 10
())(((
3 7
5 10
6 5
2 2
6 2

样例输出 1

14
14
14
9
9
6

样例输入 2

5 10
5 10 6 8 3 6 2 1 16 11
((())()(((
4 9
9 9
2 11
4 20
7 9
1 5
9 16
8 4
2 18
4 20

样例输出 2

12
12
12
12
12
12
12
12
15
15
15

样例 3~5

见下发文件。

数据范围

对于所有数据，满足 $1\le n\le 10^5$，$1\le q\le 5\times 10^5$，$0\le a_i,x\le 10^9$，$s$ 为括号串。

• subtask 1(15pts): $n,q\le 100$
• subtask 2(10pts): $n,q\le 1000$，$s$ 在所有括号串中随机生成
• subtask 3(10pts): $n,q\le 1000$
• subtask 4(5pts): $a_i=x=1$
• subtask 5(25pts): $q\le 10^5$
• subtask 6(35pts): 无特殊限制