Canadian Computing Competition: 2022 Stage 1, Senior #5
There are
and are friends, and are friends (for ), and and are friends.
Initially, each student Y
) or does not intend to
write the CCC (if N
). Initially, at least one student intends to write the CCC, and at
least one student does not intend to write the CCC.
The CCC has allocated some funds to pay some students to be influencers for the CCC.
The CCC will repeatedly choose one student
Help the CCC determine the minimum cost required to have all of the students intend to write the CCC.
Input Specification
The first line contains the integer
The next
The next line contains Y
or N
.
The next line contains
The following table shows how the available 15 marks are distributed.
Marks Awarded | Number of Students | Payment | Additional Constraints |
---|---|---|---|
None | |||
None |
Output Specification
Output the minimum integer number of dollars required to have all of the students to intend to write the CCC.
Sample Input 1
4
1 2
2 3
3 4
YNYN
4 3 6 2
Output for Sample Input 1
6
Explanation of Output for Sample Input 1
The CCC should pay $
Sample Input 2
15
1 5
5 2
2 15
15 4
2 10
8 3
3 1
1 6
11 6
12 6
11 9
11 14
12 7
13 7
NNYYYNYYNNNNNNN
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
Output for Sample Input 2
6
Explanation of Output for Sample Input 2
One optimal strategy is for the CCC to ask students
Comments