smoothie-web Problems Contests Ranking About
Login Register

BSSPC 2019 P3 - Shakespeare Insults

data_usage Points
timer Time Limit
linear_scale Memory Limit

Problem Statement

magicalsoup just used some nasty Shakespeare insults today! Sadly, his was by far not the best, thus after collecting a bit of data, he asks you to help him find the top 3 best insults.

A Shakespeare insult is comprised of 3 parts, an adjective, another adjective, then a noun.

You will be given 3 integers, NN , MM and KK, the number of adjective 1, adjective 2 and nouns.

For each adjective and noun, you will also be given a number XX, the number of points, a word will have. The best insult is the one with the collective points. In other words, an insult’s points is calculated by adding the points of adjective1, adjective2 and noun respectively.

All adjectives and nouns will be one word, composed of uppercase, lowercase letters, and the character ‘-‘ to substitute a space.

Help magicalsoup with his sore loser syndrome!

Output the answers in the form adjective 1 adjective 2 noun with a space in between each of the words.

Note: If there is a tie, output the answer that is bigger. For example, giving the 2 strings with the same value ‘a b c‘ and ‘a b d‘, String ‘a b d‘ is the answer as it is the bigger string lexicographically.

Input Specification

First line, an integer NN (1N1031 \le N \le 10^3)

Next NN lines: input will be given in the form word x, where word will be the adjective 1 and x will be the points.

Next line, an integer MM (1M1031 \le M \le 10^3)

Next MM lines: input will be given in the form word x, where word will be the adjective 2 and x will be the points.

Next line: an integer KK (1K1031 \le K \le 103)

Next KK lines: input will be given in the from word x, where word will be the nounnoun and x will be the points.

You may assume all xx values will be less than or equal to 10910^9 and bigger than or equal to 109−10^9.

You may also assume that each word length will be smaller than 30 characters.

Output Specification

On 3 separate lines, output the top 3 Shakespeare insults, each word being separated by a space. List them from best to worst.

All insults should be distinct, but a word may be used for multiple insults.

Sample Input

artless 3
base-court 6
bawdy 7
churlish 10
cockered 20
apple-john 200
baggage 4
clotpole 3
death-token 100

Sample Output

1. base-court cockered apple-john
2. artless cockered apple-john
3. base-court churlish apple-john


The first one’s score is 6+20+200=2266 + 20 + 200 = 226.

The second one’s score is 3+20+200=2233 + 20 + 200 = 223.

The third one’s score is 6+10+200=2166 + 10 + 200 = 216.