유니폼 구매하기

당신은 Saskatchewan 시골 지역의 축구 리그를 운영하는 일자리를 구했다. 이 리그는 주요 도시에서 수백 킬로미터 떨어진 곳에 있어, 팀을 단 두 개만 운영할 수 있다. Saskatchewan 시골 지역에는 달리 할 일이 거의 없기 때문에, 많은 선수가 다른 선수들과 심각한 개인적 라이벌 관계를 맺게 되었다. 이 선수들은 자신의 라이벌 중 누구와도 같은 팀에 배정되는 것을 거부한다. 지난 시즌에 당신의 전임자는 선수들의 선호를 존중하여 팀에 배정하는 방법을 찾아냈다. 새로운 스폰서와 함께하는 새 시즌이므로, 리그를 위해 새 유니폼을 구매해야 한다. 유니폼 구매 비용을 알아본 결과, 지난 시즌의 팀들을 유지하는 데 비용이 매우 많이 들 수 있다는 사실을 깨달았다. 따라서 비용을 최소화하기 위해 팀을 다시 배정하기로 했다.

• 한 팀의 선수들에게는 유니폼이 필요하며, 비용은 선수 한 명당 1달러이다.

• 다른 팀의 선수들은 유니폼 없이 경기하며, 비용은 들지 않는다.

• 일부 선수를 리그에서 제외하도록 선택할 수도 있다. 선수 한 명을 제외할 때마다 참가비를 환불해야 하므로 리그에 2달러의 비용이 든다.

최선을 다하더라도, 지난 시즌의 팀 배정이 이미 가능한 한 가장 저렴했을 수도 있다. 어떤 경우든, 라이벌인 두 선수가 같은 팀에 속하지 않고 총비용이 최소화되도록 각 선수를 유니폼 팀이나 유니폼이 없는 팀에 배정하거나 리그에서 제외하는 것이 당신의 임무이다.

입력의 첫 번째 줄에는 선수의 수와 라이벌 관계의 수를 나타내는 두 정수 $N$ ($2 \leq N \leq 2\,000$)와 $M$ ($1 \leq M \leq 5\,000$)가 주어진다. 이어지는 $M$개의 각 줄에는 선수 $u$와 $v$가 라이벌임을 나타내는 두 정수 $u$와 $v$ ($1 \leq u < v \leq N$)가 주어진다. 서로 다른 각 라이벌 관계는 단 한 번만 주어짐이 보장된다. 마지막 줄에는 이전 팀 배정을 나타내는 길이 $N$의 이진 문자열 $S$가 주어진다. 즉, 선수 $i$가 유니폼 팀에 속했다면 $S_i = 1$이고, 선수 $i$가 유니폼이 없는 팀에 속했다면 $S_i = 0$이다. 이 선수들의 팀 배정에서 라이벌인 두 선수가 같은 팀에 속하지 않음이 보장된다.

선수들을 팀에 배정하거나 리그에서 제외하는 데 필요한 최소 총비용을 나타내는 정수 하나를 출력한다.