定义一个只包括 ( 和 ) 的字符串 $ 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): 无特殊限制