## Editorial for WC '17 Finals S1 - An Interspecific Army

Remember to use this editorial

**only**when stuck, and**not to copy-paste code from it**. Please be respectful to the problem author and editorialist.**Submitting an official solution before solving the problem yourself is a bannable offence.**To minimize , it turns out that it's always optimal to pair the worst cow with the worst monkey, the second-worst cow with the second-worst monkey, and so on. To prove this, let's consider a pair of cows with combat skill levels and (such that ), and a pair of monkeys with combat skill levels and (such that ). We note that forming the pairs and can never be better than forming the pairs and . In other words, .

Having made this insight, we'll want to sort the two lists and in non-decreasing order, which can be done in time. We can then simply find and output the maximum value of over .

## Comments