Equal Total Scores
InterviewTime limit1sMemory limit128 MB
Find one card from each person to swap so their total scores match, choosing the pair with the smallest sum, or print -1.
- Level
Easy3 of 10
- Topics
- Brute force, Implementation, Array, Math
- Solved
- No attempts yet
Problem
Taro and Hanako each hold several cards, and every card has a score printed on it. They want to make the total score of the cards in their hands equal by exchanging exactly one of Taro's cards for exactly one of Hanako's cards. Decide which card should be swapped for which.
They must exchange a pair of cards even when their total scores are already equal.
Input
The input consists of several datasets. Each dataset has the following format:
n m
s1
s2
...
sn
sn+1
sn+2
...
sn+m
The first line contains two integers and separated by a space, where is the number of cards Taro has and is the number of cards Hanako has. The next lines give one score per line: the first scores ( to ) are Taro's cards, and the remaining scores ( to ) are Hanako's.
Both and are positive integers no greater than , and each score is a non-negative integer no greater than .
The end of the input is a line containing two zeros separated by a single space; do not process it.
Output
For each dataset, print one line with two integers separated by a single space: the score of the card Taro gives to Hanako, followed by the score of the card Hanako gives to Taro. If several exchanges make the totals equal, print the pair whose sum is the smallest.
If no exchange can make the totals equal, print a single line containing only . The output must not contain any extra characters.