Metro
The mayor of Catlandia's capital has finally decided to construct a metro network in the city. His primary goal is to minimize the construction costs of this metro system.
The metro network will include several stations connected by bidirectional tunnels. There must be a path through these tunnels between any two stations (possibly passing through other stations), and the number of tunnels should be minimized. Under these conditions, there will be a unique path between any two stations.
Passengers will pay a fee to enter the metro at a specific station. This fee varies by station and is determined by the maximum number of tunnels a passenger must travel through to reach any other station from a given station X. This fee is measured in hryvnias.
Additionally, the mayor has specific numerical preferences. He loves certain numbers A[1], ..., A[N] and hates others B[1], ..., B[M]. The metro cannot be constructed unless all of his favorite numbers appear among the entry costs at the stations, and none of the numbers he hates are present.
Task
Write a program that, given the mayor's numerical preferences, determines the minimum number of stations needed for the metro, or concludes that constructing such a network is impossible.
Input
The first line contains two integers N and M — the count of numbers the mayor loves and hates, respectively. The second line lists N integers, separated by spaces — the numbers the mayor loves. The third line lists M integers in the same format — the numbers the mayor hates.
Output
Output a single line with the minimum number of stations required for the metro. If it is impossible to construct a network meeting the requirements, output -1.
Evaluation
The test set is divided into two blocks with the following conditions:
For 50% of the points:
1 ≤ N, M, A[i], B[i] ≤ 2000.For the remaining 50% of the points:
1 ≤ N, M, A[i], B[i] ≤ 100000.