Chess Teams

In a classroom, there are N students. Each of them is either a boy or a girl.

Sometimes, the boys are arguing with each other because of some girl. Other times, some girls fight with each other because of the boys. But a boy never argues with a girl or vice versa. This is why there are some pairs of boys and some pairs of girls who cannot be in the same team. We will call such pairs of students incompatible.

You want to select a team for the national chess competition. For this, you will consider each student's ELO rating (a rating that indicates how good a student is at chess). The rating of a team is the sum of the ratings of all its members.

Some subset of students can form a team if

• the number of girls in the team equals the number of boys, and
• there are no two incompatible students in the team.

You must find the maximum rating of a valid team.

Input Specification

The first line of the input contains the number N (1 ≤ N ≤ 40).

Each of the next N lines contains the description of a student: a character representing the gender of the student (g for girl and b for boy) and an integer E representing their ELO rating (0 ≤ E ≤ 5000).

Then, the next line will contain a number M, the number of pairs of incompatible students (1 ≤ M ≤ N · (N – 1) / 2).

Each of the next M lines will contain two integers, denoting the indexes of a pair of students who are incompatible (indexing starts from 1 with the first student). It is guaranteed that for each pair of students, they are either both boys or both girls.

Output Specification

Output a single integer, the maximum ELO rating of a valid team.

Sample Input

1. 6
2. b 253
3. b 1253
4. g 5000
5. g 1
6. g 2
7. g 3
8. 3
9. 3 4
10. 3 5
11. 3 6

download as text file

Output for Sample Input

1. 6253

download as text file