#P18762. [2025NA]Buying Jerseys

[2025NA]Buying Jerseys

题目描述

一项足球联赛中共有 NN 名球员。球员之间有 MM 对互相不愿同队的关系,称为对手关系。每名球员可以采取以下三种安排之一:

  1. 加入穿球衣的球队,费用为 11;
  2. 加入不穿球衣的球队,费用为 00;
  3. 退出联赛,退费成本为 22。

对任意一对存在对手关系的球员,如果他们都没有退出,则不能被安排进同一支球队。

题目保证上一赛季存在一种将全部球员分配到两队、且不违反对手关系的方案。这一方案会以二进制字符串给出,其中 1 表示穿球衣的球队,0 表示不穿球衣的球队。

本赛季允许重新分队,也可以让部分球员退出。求所有安排中,联赛承担的最小总费用。

输入格式

第一行包含两个整数 N,MN,M,满足:

2≤N≤2000,1≤M≤5000.2\le N\le 2000,\qquad 1\le M\le 5000.

接下来 MM 行,每行两个整数 u,vu,v(1≤u<v≤N1\le u<v\le N),表示球员 uu 与 vv 是对手。每对关系仅出现一次。

最后一行是长度为 NN 的二进制字符串 SS。若 Si=1S_i=1,表示球员 ii 上赛季在穿球衣队,否则在不穿球衣队。保证 SS 对所有对手关系均合法。

输出格式

输出一个整数,即最小总费用。

样例 1

输入

4 1
1 2
0101

输出

1

样例 2

输入

4 4
1 2
3 4
1 4
2 3
0101

输出

2

样例 3

输入

8 7
1 2
1 3
1 4
1 5
2 6
2 7
2 8
01111000

输出

3