Description
It is now the year 2023, and the CS student association is going to throw a dance party once again. On the whole, the rules are quite similar to the ones in 13532 - Promenade Dance, where the objective was to avoid crisscrossed ribbons and maximise the number of paired couples.
However, there are some changes this year. First and foremost, each boy is able to know the exact name of the girl he had invited (at least in most cases).
What's more, the CS student association measured the happiness value, i.e., the amount of disappointment if one is not selected and the amount of happiness if one is selected, of each boy. Since we would like to make the atmosphere of the party cheerful and see fewer people upset, we shall select the pairs in such a way that the sum of their happiness values is maximum.
Input
There's an integer \(N\) in the first line, indicating the number of boys / girls. The second line consists of \(N\) strings \(B_i\) which are the names of girls invited by \(i^\text{th}\) boy. The third line are \(N\) strings \(G_i\) which are the names of girls . The last line would be \(N\) integers \(W_i\) representing the happiness values. For the sake of your simplicity, they would come in the same order as the girls the boys have invited.
It is guaranteed that the names consist only of English letters and numbers, have a length of at most 10, and are unique, and that \(B\) is a permutation of \(G\) and \(N<10^6\).
- In 40% of the testcases, the happiness values are always 1 and the names of girls' are \(1,2\dots N\). Alhough this sounds peculiar, you might consider this subtask is well-nigh identical to 13532 - Promenade Dance.
- In another 40% of the testcases, the happiness values are still always 1. You could solve this subtask as well probably if you could solve 13532 - Promenade Dance with some slight extra codes.
- In the last 20% of the testcases, the happiness values varies. It may be far more challenging.
Output
Please print out the maximum sum of happiness values we could select.
Explanation
Let's take above figure as instance. Suppose that boys had invited Leia, Padmé, Jyn, Rey, Rose & Dormé, respectively, and the girls are Leia, Dormé, Padmé, Jyn, Rose & Rey sequentially.
If the happiness values of 6 boys are all 1, then this circumstance is reduced to the sample in 13532 - Promenade Dance. In this case, we should select Leia, Padme, Jyn & Rey (or one may select Leia, Padme, Jyn & Rey alternatively), resulting an the answer of 4.
On the other hand, if the happiness values of 6 boys are 1, 9, 3, 3, 1 & 1, respectively, then the optimal selection would be Leia & Dormé and the answer is thus \(1+9=10\), whereas the original selection would yield a sum of \(1+3+3+1=8\).