Davidku and Otasu are brothers who love ACG(Anime, Comic and Game) very much. Due to their professional skills and
knowledge on ACG, everybody called them "Super OTAKU brothers".
One day, an new video game, "Tales of KoKuHaKu in the end of century" is published. The game is a typical love simulation
game that you have to interactive with each girls in the games and make decisions in the conversation.
For the relationships between you and each girls, there are numerical values representing how good it is and how the girl likes
you, called L-value. Some events would arise depending on your conversation decisions and therefore it matter the L-values of
girls and the ending of story. So if you like some girls, you may try raising the L-values with them.
To live up to their reputation, the name of "Super OTAKU brothers", this time they also want to write the playing guide
of the game to other video game players on internet.
Now they want to make a section in the guide talking about "What events must arise to maximize the L-values of the girls?".
After disassembling the game and tracing the code, they know the rules about the changing of L-values.
For every event E, there is a corresponding set S(E) consisting of elements indicating how it affects the L-values of girls.
Every element is a pair of value (N, V) repsenting the name of girl and the variation of L-value.
For example, let S(E) = {(Raou, 5), (Kenshirou, -2)}. Then if you arise the event E, Raou's L-value would increase by 5 and Kenshirou's L-value would decrease by 2.
In addition, when you arise two events E and F, for this two events, if the number of girls who participates in exactly
one of the two events is a prime number more than 2(excluded), these girls would be resentful and their L-values would decrease
by the square of the prime number (what a geek design).
For example, suppose there are two events E and F, and S(E) = {(Raou, 10), (Kenshirou, -10), (Toki, -5)}, S(F) = {(Kenshirou, 20), (Yuria, 5)}.
Then if you arise both the events, The variation of L-values is the following result.
Kenshirou: -10 + 20 = +10
Raou: +10 - 3 * 3 = +1
Toki: -5 - 3 * 3 = -14
Yuria: 5 - 3 * 3 = -4
Now they want someone to help them. You are to write a program that they can import the event data and indicate
which girls they want to maximize the L-value. Then the program would find out what events should arise to maximize the sum of L-values of the indicated girls .
For each case, output a single line containing the maximum L-value they can achieve.