描述
魔法师小B在探险途中来到一座神殿。为了获得神殿中的宝藏，他需要完成一场召唤仪式。
神殿的地面上刻有 $n$ 个魔法阵，编号为 $1,2,\ldots,n$。魔法阵之间共有 $m$ 条纹路，每条纹路连接两个不同的魔法阵，任意两个魔法阵之间至多有一条纹路。
从任意一个魔法阵出发，沿纹路能够到达的**所有魔法阵**，以及这些魔法阵之间的全部纹路，共同构成一个**魔法图案**。（这里仅根据纹路的连接关系判断，与下文提到的传送门的方向以及是否开启无关。）如果一个魔法阵没有连接任何纹路，它单独构成一个魔法图案。
小B观察到，这座神殿中的魔法图案都具有一个特点：**每个魔法图案中，纹路的条数不超过魔法阵的个数。**
例如，一座神殿中有 $7$ 个魔法阵，五条纹路分别连接 $1$ 号与 $2$ 号魔法阵、$2$ 号与 $3$ 号魔法阵、$3$ 号与 $1$ 号魔法阵、$3$ 号与 $4$ 号魔法阵，以及 $5$ 号与 $6$ 号魔法阵。这座神殿中共有三个魔法图案：
| 魔法图案包含的魔法阵 | 魔法阵的个数 | 纹路的条数 |
|:---|:---:|:---:|
| 1、2、3、4 号魔法阵 | 4 | 4 |
| 5、6 号魔法阵 | 2 | 1 |
| 7 号魔法阵 | 1 | 0 |
其中，**1、2、3 号魔法阵以及它们之间的纹路，不能单独构成一个魔法图案。**虽然这三个魔法阵之间有纹路相连，但从 3 号魔法阵还能够沿纹路到达 4 号魔法阵，因此必须将 4 号魔法阵和连接它的纹路一起包括进来。7 号魔法阵没有连接任何纹路，所以它单独构成一个魔法图案。
每个魔法阵最多放置一块黑曜石。召唤仪式开始前，小B可以选择一些魔法阵，各放置一块黑曜石，其余魔法阵上不放置黑曜石。在第 $i$ 个魔法阵上放置一块黑曜石，需要消耗 $w_i$ 点魔力；不放置则不消耗魔力。所有黑曜石都相同，小B可以自行决定放置黑曜石的数量和位置。
每条纹路对应一道单向传送门，传送门的方向和开启时刻都已由神殿规定好。召唤仪式开始后，在第 $1,2,\ldots,m$ 个时刻，每个时刻恰好开启一道传送门，每道传送门恰好开启一次。
第 $j$ 个时刻开启的传送门从魔法阵 $u_j$ 通向魔法阵 $v_j$，对应连接这两个魔法阵的纹路。如果魔法阵 $u_j$ 上有一块黑曜石，并且魔法阵 $v_j$ 上没有黑曜石，那么这块黑曜石必须传送到魔法阵 $v_j$，魔法阵 $u_j$ 上不再有黑曜石；否则不发生传送。特别地，如果两个魔法阵上都有黑曜石，那么两块黑曜石都留在各自的魔法阵上，不会交换位置。每道传送门开启时只按照上述规则处理一次，随后立即关闭。
同一个魔法阵可以在不同时刻作为传送的起点或终点，也可以向不同的魔法阵传送黑曜石。黑曜石到达一个魔法阵后，不会自动触发其他传送门。纹路始终存在，但只有对应的传送门开启时，才可能发生传送。
召唤仪式开始后，小B不能再增添、取走或者手动移动黑曜石，也不能改变传送门的方向和开启顺序。传送门会在规定的时刻自动开启，开启传送门和传送黑曜石都不额外消耗小B的魔力。
神殿规定了召唤仪式结束时各个魔法阵需要满足的要求。这些要求用一个长度为 $n$ 的字符串 $d$ 表示：
- $d_i=\texttt{1}$：第 $i$ 个魔法阵上必须有一块黑曜石；
- $d_i=\texttt{0}$：第 $i$ 个魔法阵上必须没有黑曜石；
- $d_i=\texttt{?}$：第 $i$ 个魔法阵上是否有黑曜石均可。
所有传送门依次开启并关闭后，检查上述要求。当 $m=0$ 时，直接检查黑曜石放置后的状态。只有全部要求同时满足，召唤仪式才算完成，宝藏才会出现。请帮助小B决定仪式开始前黑曜石的放置方案，求出完成召唤仪式所需消耗的最小魔力总量。如果不存在满足要求的放置方案，输出 $-1$。
输入
第一行包含一个整数 $T$，表示数据组数。每组数据依次给出：
第一行包含两个整数 $n,m$，分别表示魔法阵的个数和纹路的条数。
第二行包含 $n$ 个整数 $w_1,w_2,\ldots,w_n$，其中 $w_i$ 表示仪式开始前在第 $i$ 个魔法阵上放置一块黑曜石需要消耗的魔力。
第三行包含一个长度为 $n$ 的字符串 $d$，表示召唤仪式结束后各个魔法阵需要满足的要求。
接下来共有 $m$ 行。第 $j$ 行包含两个整数 $u_j,v_j$，表示第 $j$ 个时刻开启的传送门从魔法阵 $u_j$ 通向魔法阵 $v_j$。这两个魔法阵之间有一条纹路，全部 $m$ 行恰好对应神殿中的全部 $m$ 条纹路。
输出
对于每组数据，输出一行，包含一个整数，表示完成召唤仪式所需消耗的最小魔力总量。如果不存在满足要求的放置方案，输出 $-1$。
样例
- 复制
- 复制
提示
## 样例解释
下面用 `0` 表示魔法阵上没有黑曜石，用 `1` 表示魔法阵上有一块黑曜石，并按照魔法阵编号从小到大的顺序记录状态。
第 1 组样例中，四个魔法阵属于同一个魔法图案，其中共有四个魔法阵、三条纹路，满足题目中的数量限制。小B在 2 号魔法阵和 3 号魔法阵上各放置一块黑曜石，消耗 $1+6=7$ 点魔力。初始状态为 `0110`，三个时刻的传送门依次关闭后，状态分别为 `1010`、`1010`、`1001`，满足全部要求。第 2 个时刻虽然没有发生传送，但对应的传送门仍然会关闭。仪式结束时，1 号魔法阵和 4 号魔法阵上都必须有黑曜石，因此初始至少放置两块黑曜石；放置黑曜石所需魔力最少的两个魔法阵正是 2 号魔法阵和 3 号魔法阵，所以 $7$ 点魔力就是最小值。
第 2 组样例中，只需在 2 号魔法阵上放置一块黑曜石。第 1 个时刻，这块黑曜石传送到 1 号魔法阵；第 2 个时刻，2 号魔法阵上没有黑曜石，因此没有发生传送。仪式结束时的状态为 `100`，总共消耗 $1$ 点魔力。
第 3 组样例只交换了第 2 组样例中两道传送门的开启顺序。如果只在 2 号魔法阵上放置黑曜石，它会先传送到 3 号魔法阵，之后无法到达 1 号魔法阵。由于最终要求恰有一块黑曜石，而传送不会改变黑曜石的总数，因此初始也只能放置一块黑曜石。依次尝试在三个魔法阵上放置黑曜石后，只有初始在 1 号魔法阵上放置黑曜石的方案满足要求，需要消耗 $8$ 点魔力。
第 4 组样例中，唯一的传送门从 1 号魔法阵通向 2 号魔法阵。若传送门开启前只有 1 号魔法阵上有黑曜石，这块黑曜石就必须传送到 2 号魔法阵；其余初始状态也不能得到 `10`。因此不存在满足要求的放置方案，输出 $-1$。
第 5 组样例中，没有纹路，也不会开启传送门。唯一的魔法阵单独构成一个魔法图案，小B必须在仪式开始前放置一块黑曜石，消耗 $9$ 点魔力。
第 6 组样例中，只在 1 号魔法阵上放置黑曜石会使它被传送走，只在 2 号魔法阵上放置黑曜石又不能让 1 号魔法阵上有黑曜石。因此必须在两个魔法阵上都放置黑曜石，使这一次传送不能发生，总共消耗 $3+8=11$ 点魔力。2 号魔法阵的最终状态虽然没有限制，但初始在 2 号魔法阵上放置黑曜石仍然是必要的。
## 数据范围与测试点
对于所有数据，保证：
- $1\le T\le1000$，$1\le n\le2\times10^5$，$0\le m\le n$；
- $0\le w_i\le10^9$，同一输入文件中所有数据组的 $n$ 之和不超过 $2\times10^5$；
- $d_i\in\{\texttt{0},\texttt{1},\texttt{?}\}$，$1\le u_j,v_j\le n$，且 $u_j\ne v_j$；
- 任意两个魔法阵之间至多有一条纹路；
- 每个魔法图案中，纹路的条数不超过魔法阵的个数。
记 $D$ 为神殿中各个魔法图案所包含的魔法阵个数的最大值。没有连接任何纹路的魔法阵单独构成一个魔法图案，其中有 $1$ 个魔法阵、$0$ 条纹路。
下表中的限制对对应测试点中的每组数据均成立。“—”表示除上述通用数据范围外，没有额外限制。同一行列出多个特殊性质时，这些特殊性质同时成立。
| 测试点编号 | $n$ | $D$ | $T$ | 特殊性质 | 分值 |
|:---:|:---:|:---:|:---:|:---:|:---:|
| 1 | — | — | — | $m=0$ | 5 |
| 2 | $n\le18$ | — | $T\le20$ | — | 5 |
| 3 | $n\le18$ | — | $T\le20$ | — | 5 |
| 4 | — | $D\le8$ | — | — | 5 |
| 5 | — | $D\le8$ | — | — | 5 |
| 6 | — | — | — | A | 5 |
| 7 | — | — | — | A | 5 |
| 8 | — | — | — | B、C | 5 |
| 9 | — | — | — | B、C | 5 |
| 10 | — | — | — | B | 5 |
| 11 | — | — | — | C | 5 |
| 12 | — | — | — | C | 5 |
| 13 | — | — | — | C | 5 |
| 14 | — | — | — | C | 5 |
| 15 | — | — | — | — | 5 |
| 16 | — | — | — | — | 5 |
| 17 | — | — | — | — | 5 |
| 18 | — | — | — | — | 5 |
| 19 | — | — | — | — | 5 |
| 20 | — | — | — | — | 5 |
**特殊性质 A：**对于每个至少包含一条纹路的魔法图案，都存在一个魔法阵 $c$，使这个魔法图案中的每条纹路都有一端连接魔法阵 $c$。
**特殊性质 B：**每个魔法阵直接连接的纹路不超过两条。
**特殊性质 C：**每个魔法图案中，纹路的条数都比魔法阵的个数少 $1$。
每个测试点单独计分，每个测试点为 $5$ 分，总分为 $100$ 分。一个测试点输入文件中的所有数据组均回答正确时，获得该测试点的分值。
关注我们
