魔法师小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。