Helmet and Vest

Interview

Time limit1sMemory limit512 MB

Summary

Given a list of helmet defense values and a list of vest values, print the sum of the best helmet and the best vest.

Level: Easy1 of 10
Topics: Array, Implementation, Brute force, Math
Solved: No attempts yet

Problem

In the game Battlegrounds, a player wears a helmet and a vest to protect the head and the body.

The map holds many helmets and vests, and each one has its own defense value. A player can wear at most one helmet and at most one vest. Gyeongsu wants to win, so he is willing to spend the time it takes to pick up the best helmet and the best vest and reach the highest defense.

Given the defense values of the helmets and the vests on the map, find the largest defense Gyeongsu can reach.

Input

The first line contains the number of helmets $N$ and the number of vests $M$ on the map. $N$ and $M$ are natural numbers not greater than 1000. The second line contains the defense value $h_i$ of each helmet, $N$ values in total. The third line contains the defense value $a_i$ of each vest, $M$ values in total. Every defense value is a natural number not greater than 1 billion.

Output

Print the largest defense Gyeongsu can reach.

Examples2

Example 1
Input
```
5 7
10 60 15 20 7
1 2 3 7 5 1 3
```
Expected output
```
67
```

Example 2

Input

2 3
1 1000000000
20 18 1000000000

Expected output

2000000000