BSSPC 2019 P3 - Shakespeare Insults

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, $N$ , $M$ and $K$, the number of adjective 1, adjective 2 and nouns.

For each adjective and noun, you will also be given a number $X$, 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 $N$ ($1 \le N \le 10^3$)

Next $N$ 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 $M$ ($1 \le M \le 10^3$)

Next $M$ 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 $K$ ($1 \le K \le 103$)

Next $K$ lines: input will be given in the from word x, where word will be the $noun$ and x will be the points.

You may assume all $x$ values will be less than or equal to $10^9$ and bigger than or equal to $−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

2
artless 3
base-court 6
3
bawdy 7
churlish 10
cockered 20
4
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

Explanation

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

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

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