Krizhanovsky's Lot

Time limit2.002sMemory limit1024 MB

Summary

Given all players' prior scores and the numbers already said this round, choose Petya's number to maximize how many players end with fewer total points than him, breaking ties by the smallest number.

Level: Medium4 of 10
Topics: Implementation, Brute force, Greedy, Math
Solved: No attempts yet

Problem

Petya and his friends play a game that is sometimes called <<Krizhanovsky's Lot>>. The rules are as follows. In each round every player thinks of an arbitrary positive integer. Then the player who thought of the smallest number that is not repeated wins the round, and his winnings equal that number. For example, if 6 people play and the numbers 3, 2, 1, 1, 4, 2 were thought of, then the first player wins, and his winnings are 3. If every number that was thought of is repeated, the round is a draw and no one gets points.

A player's total winnings for the game equal the sum of the points from all rounds played.

When Petya and his friends play, they simply say the numbers they thought of in turn, and then determine who won and count the points. With this format, however, a player can in principle cheat: instead of fixing a number in advance, after already knowing the numbers said by the previous players, he can choose an optimal <> number for himself. This is what Petya does. He says his number last and tries to choose it so as to maximize his winnings.

The last round of the game is under way. The scores of all players before this round and the numbers the players said are known. Determine what number Petya should say so that, in the results of the game, as many players as possible have fewer points than he does. If there are several such numbers, Petya wants to say the smallest possible one.

Input

The first line of the input file contains the number $n$ , the number of players ( $2 \le n \le 100$ ). The second line contains $n$ numbers: the players' scores before the last round (non-negative integers not greater than 100). The scores are listed in the order in which the players usually say their numbers, that is, Petya's score is last. The third line contains $n - 1$ numbers: the numbers said by the players in the last round (the numbers do not exceed 100), in the order in which they said them.

Output

Print to the output file the number Petya should say.

Notes

In the second example Petya cannot win the last round. However, by saying the number 2, Petya prevents the first player from winning and thus remains second in the overall game. Four players have fewer points than Petya.

Examples2

Example 1
Input
```
6
0 0 0 0 0 0
2 3 4 5 6
```
Expected output
```
1
```
Example 2
Input
```
6
8 3 12 5 0 9
2 1 3 1 4
```
Expected output
```
2
```