Metro#7666
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 . This fee is measured in hryvnias.
Additionally, the mayor has specific numerical preferences. He loves certain numbers A_1, \ldots, A_N and hates others B_1, \ldots, 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.
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.
The first line contains two integers and — the count of numbers the mayor loves and hates, respectively. The second line lists integers, separated by spaces — the numbers the mayor loves. The third line lists integers in the same format — the numbers the mayor hates.
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 .
Example 1
Example 2
The test set is divided into two blocks with the following conditions:
of the points: 1 \leq N, M, A_i, B_i \leq 2000.
of the points: 1 \leq N, M, A_i, B_i \leq 100000.