Marriage agency P50538


Statement
 

pdf   zip

html

A marriage agency has n customers of both sex. It is known the age of all the customers (expressed with the same unit for everybody, and it does not have to be years; it could be months, days, etc). The two people in charge of the agency have different opinions about how the customers should be paired off. One of them thinks that the sum of the differences of ages of each formed pair should be minimized. The other one thinks just the opposite think, that is, that the sum of the differences should be maximized.

Write a program that computes the minimal possible sum of differences and the maximal possible sum of differences. For instance, if n = 2, the men are 25 and 40, and the women are 20 and 50, then there only are two possibilities: 25–20, 40–50 (with total sum 15) and 40–20, 25–50 (with total sum 45).

Input

The input consists of 1≤ n ≤ 50000, followed by n numbers in a line with the ages of the men, followed by n numbers in other line with the ages of the women.

Output

Your program must print a line with two numbers separated by a space: the minimal possible sum of the differences of ages, and the maximal possible sum of the differences of ages.

Public test cases
  • Input

    2
    25 40
    20 50
    

    Output

    15 45
    
  • Input

    4
    65 18 65 24
    24 20 50 24
    

    Output

    58 118
    
  • Input

    1
    80
    58
    

    Output

    22 22
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Translator
    Carlos Molina
    Original language
    Spanish
    Other languages
    Spanish
    Official solutions
    C++
    User solutions
    C++