Problem B
Buying Jerseys

You have found a job managing a soccer league in rural Saskatchewan. This league is located several hundred kilometers from any major city, and so has capacity for only two teams. Because there is little else to do in rural Saskatchewan, many players have developed bitter personal rivalries with other players. These players will refuse to be put on a team with any of their rivals. Last season, your predecessor found a way to assign players to teams that respects their preferences. Since it is a new season with new sponsors, you must purchase new jerseys for the league. After looking into the cost of buying jerseys, you have realized that last season’s teams may be very expensive to support. Thus, you have decided to re-assign teams in order to minimize costs.

• Players on one team require jerseys, which cost one dollar per player.

• Players on the other team play without jerseys, at no cost.

• You may also choose to remove some players from the league. Removing a player costs the league two dollars each because their entry fee has to be refunded.

Despite your best efforts, it may be the case that last season’s team assignment may already have been as cheap as possible. Regardless, your job is to assign each player to either the jersey team, the no-jersey team, or remove them from the league, so that no pair of rivals ends up on the same team, and the total cost is minimized.

Input

The first line of input contains two integers $N$ ($2 \leq N \leq 2\, 000$) and $M$ ($1 \leq M \leq 5\, 000$) representing the number of players and number of rivalries. Each of the following $M$ lines contains two integers $u$ and $v$ ($1 \leq u < v \leq N$) indicating that players $u$ and $v$ are rivals. It is guaranteed that each unique rivalry is listed only once. The final line contains a binary string $S$ of length $N$ representing the previous team assignment. That is, $S_i = 1$ if player $i$ was on the jersey team, and $S_i = 0$ if player $i$ was on the no-jersey team. It is guaranteed that this assignment of players to teams does not put any pair of rivals on the same team.

Output

Output a single integer representing the minimum total cost required to assign players to teams or remove them from the league.

4 1
1 2
0101

1

4 4
1 2
3 4
1 4
2 3
0101

2

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

3