Cost of removal#3646
An undirected graph is provided, which contains no loops or multiple edges. The vertices in this graph are categorized into two types: black and white. A black vertex will disappear if it has no adjacent white vertices, and similarly, a white vertex will vanish if it has no adjacent black vertices. Each vertex has a known removal cost. Your task is to determine the minimum cost required to remove all vertices from the graph.
The input begins with two integers, and : the number of vertices and the number of edges in the graph, respectively, where 1 \le n \le 100 and 0 \le k \le n \cdot (n - 1) / 2. This is followed by lines, each containing two integers, and . Here, indicates the type of the vertex ( for white, for black), and represents the cost of removing that vertex, with 1 \le c \le 10^6. After this, lines follow, each containing two integers, and , which specify the vertices connected by an edge, where 1 \le a, b \le n.
The output should be a single integer representing the minimum cost to remove all vertices from the graph.
Example 1