Card game
Tag(s):

Algorithms, Easy, Quicksort

Problem
Editorial
Analytics

Two friends decided to play a very exciting online card game. At the beginning of this game, each player gets a deck of cards, in which each card has some strength assigned. After that, each player picks random card from his deck and they compare strengths of picked cards. The player who picked card with larger strength wins. There is no winner in case both players picked cards with equal strength.

First friend got a deck with n cards. The i-th his card has strength $a_i$. Second friend got a deck with m cards. The i-th his card has strength $b_i$.

First friend wants to win very much. So he decided to improve his cards. He can increase by 1 the strength of any card for 1 dollar. Any card can be improved as many times as he wants. The second friend can't improve his cards because he doesn't know about this possibility.

What is the minimum amount of money which the first player needs to guarantee a victory for himself?

Input format

The first line of the input contains single integer n ($1 \leq n \leq 3 \cdot 10^5$) - the number of first friend's cards.

The second line of the input contains n space separated integers $a_i$ ($1 \leq a_i \leq 10^9$) - the strength of the i-th first friend's card.

Second friend's cards are given in the next two lines in the same format.

Output format

Print single integer - the minimum amount of money which the first friend needs to guarantee a victory for himself.

SAMPLE INPUT
3
1 3 10
2
3 4

SAMPLE OUTPUT
6

Explanation

For 6 dollars first player can improve cards from $[1, 3, 10]$ to $[5, 5, 10]$. Second player has cards $[3, 4]$. All possible game situations:

1. $a_1 = 5 > b_1 = 3$
2. $a_1 = 5 > b_2 = 4$
3. $a_2 = 5 > b_1 = 3$
4. $a_2 = 5 > b_2 = 4$
5. $a_3 = 10 > b_1 = 3$
6. $a_3 = 10 > b_2 = 4$

First player always wins.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 512 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...

Contributor Challenge Name

October Circuits '17

OTHER PROBLEMS OF THIS CHALLENGE
• Math > Linear Algebra
• Algorithms > Graphs
• Math > Counting
• Algorithms > String Algorithms
• Data Structures > Advanced Data Structures
• Data Structures > Advanced Data Structures