括号匹配

题号：NC267139
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

给出一个长度为 $n$ 的括号序列（不保证合法）第 $i$ 个位置上的字符为 $c_i$ ，删掉 $c_i$ 的代价为 $w_i$ 。

有 $m$ 个限制形如 $(x,y,z)$ ，表示第 $x,y,z$ 个字符中只能恰好保留一个。保证一个位置至多位于一个三元组中，且对于每个三元组 $(x,y,z)$ ，都有 $c_x=c_y=c_z$ 。

若一个位置没有在约束条件中出现过，则必须保留。

询问在满足所有约束条件后，括号序列是否能变成合法括号序列。如果不能输出 No，否则输出 Yes 和在括号序列合法前提下的最小代价。

输入描述:

第一行两个数 。

第二行一个长度为  的括号串 ，仅包含 (，)。

第三行  个数，即 。

接下来  行，每行三个数，即三元组 。

输出描述:

第一行输出 No 或 Yes。

若第一行为 Yes，则在第二行输出最小代价。

示例1

输入

复制

12 2
(()(())()))(
1 0 0 1 1 0 1 0 1 1 0 1
1 2 12
9 10 11

输出

复制

Yes
2

说明

删去字符 ，代价为 ，此时括号序列合法。

备注:

对于  的数据，。