你在萨斯喀彻温省（Saskatchewan）的乡村地区找到了一份管理足球联赛的工作。该联赛距离任何大城市都有几百公里，因此只能容纳两支球队。由于在萨斯喀彻温省的乡村地区几乎没有其他娱乐活动，许多球员之间产生了激烈的个人恩怨。这些球员拒绝与他们的任何死敌分在同一支球队。上个赛季，你的前任找到了一种符合他们意愿的球员分队方案。由于这是一个有新赞助商的新赛季，你必须为联赛购买新的队服。在调查了购买队服的成本后，你意识到维持上赛季的分队方案可能会非常昂贵。因此，你决定重新分配球队以最小化成本。

• 其中一支球队的球员需要队服，每名球员的花费为 1 美元。
• 另一支球队的球员不需要队服，花费为 0 美元。
• 你也可以选择将某些球员从联赛中除名。将一名球员除名需要花费联赛 2 美元，因为必须退还他们的报名费。

尽管你付出了最大努力，但上赛季的分队方案可能已经是最便宜的了。无论如何，你的任务是将每名球员分配到有队服的球队、无队服的球队，或者将他们从联赛中除名，使得没有任何一对死敌被分在同一支球队，且总花费最小。

输入格式

输入的第一行包含两个整数 $N$（$2 \le N \le 2\,000$）和 $M$（$1 \le M \le 5\,000$），分别表示球员人数和死敌关系的数量。

接下来的 $M$ 行，每行包含两个整数 $u$ 和 $v$（$1 \le u < v \le N$），表示球员 $u$ 和球员 $v$ 是死敌。保证每对死敌关系只会被列出一次。

最后一行包含一个长度为 $N$ 的二进制字符串 $S$，表示上赛季的分队方案。也就是说，如果球员 $i$ 在有队服的球队，则 $S_i = 1$；如果球员 $i$ 在无队服的球队，则 $S_i = 0$。保证该初始分队方案中，没有任何一对死敌被分在同一支球队。

输出格式

输出一个整数，表示将球员分配到球队或将他们除名所需的最小总花费。

样例

输入样例 1

4 1
1 2
0101

输出样例 1

1

输入样例 2

4 4
1 2
3 4
1 4
2 3
0101

输出样例 2

2

输入样例 3

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

输出样例 3

3