魔法师小B在探险途中来到一座神殿。为了获得神殿中的宝藏，他需要完成一场召唤仪式。

神殿的地面上刻有 n 个魔法阵，编号为 1,2,\ldots,n。魔法阵之间共有 m 条纹路，每条纹路连接两个不同的魔法阵，任意两个魔法阵之间至多有一条纹路。

从任意一个魔法阵出发，沿纹路能够到达的所有魔法阵，以及这些魔法阵之间的全部纹路，共同构成一个魔法图案。（这里仅根据纹路的连接关系判断，与下文提到的传送门的方向以及是否开启无关。）如果一个魔法阵没有连接任何纹路，它单独构成一个魔法图案。

小B观察到，这座神殿中的魔法图案都具有一个特点：每个魔法图案中，纹路的条数不超过魔法阵的个数。

例如，一座神殿中有 7 个魔法阵，五条纹路分别连接 1 号与 2 号魔法阵、2 号与 3 号魔法阵、3 号与 1 号魔法阵、3 号与 4 号魔法阵，以及 5 号与 6 号魔法阵。这座神殿中共有三个魔法图案：

其中，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 条纹路。

下表中的限制对对应测试点中的每组数据均成立。“—”表示除上述通用数据范围外，没有额外限制。同一行列出多个特殊性质时，这些特殊性质同时成立。

特殊性质 A：对于每个至少包含一条纹路的魔法图案，都存在一个魔法阵 c，使这个魔法图案中的每条纹路都有一端连接魔法阵 c。

特殊性质 B：每个魔法阵直接连接的纹路不超过两条。

特殊性质 C：每个魔法图案中，纹路的条数都比魔法阵的个数少 1。

每个测试点单独计分，每个测试点为 5 分，总分为 100 分。一个测试点输入文件中的所有数据组均回答正确时，获得该测试点的分值。

2026第五届青少年编程挑战精英赛