House Rental

Acmi is a medium-sized city with one long main street running from west to east. Every facility in Acmi, such as a supermarket, a school, a train station, a bus stop, or a hospital, sits on that main street. You are going to rent a house on the main street, and location is what you care about most when you choose one. You have a list of $k$ facility types, and you want the distance to each of those types to be as small as possible. If a supermarket matters to you and is on your list, you want the house to be near a supermarket.

When $k = 1$ the problem is easy, because you rent the house right in front of any facility of the type you want. In the general case with $k > 1$ that strategy stops working.

Given $n$ facilities of $k$ different types along the main street, write a program that finds a best location for your house, one that minimizes the largest of the distances to the nearest facility of each type. The location of every building on the main street is an integer from $-1000000000$ to $1000000000$, and the smaller the location number, the further west the building is. The distance between two buildings is the difference of their location numbers. Two or more facilities may share one location, and each of the $k$ types has at least one facility. A vacant house you can rent is available at every integer location.

The first line contains two integers $k$ and $n$ ($1 \le k \le 100000$, $k \le n \le 1000000$), where $k$ is the number of facility types and $n$ is the number of facilities along the main street.

Each of the next $n$ lines describes one facility with two integers: its location on the street, between $-1000000000$ and $1000000000$ inclusive, and its type, between $1$ and $k$.

Print one line with one integer, a best location for your house. If two or more locations are best, print the smallest location number among them.