집 구하기

아크미는 중간 규모의 도시로, 서쪽에서 동쪽으로 길게 뻗은 중앙로가 하나 있다. 슈퍼마켓, 학교, 기차역, 버스 정류장, 병원처럼 아크미의 모든 시설은 이 중앙로에 있다. 당신은 중앙로에 있는 집을 하나 빌리려 하고, 집을 고를 때 위치를 가장 중요하게 본다. 특히 시설 종류 $k$개를 목록으로 정해 두고 각 종류까지의 거리를 되도록 줄이고 싶다. 예를 들어 슈퍼마켓을 중요하게 여겨 목록에 넣었다면 집이 슈퍼마켓 가까이에 있기를 바란다.

$k = 1$이면 원하는 종류의 시설 바로 앞에 집을 빌리면 되므로 문제가 쉽다. 하지만 $k > 1$인 일반적인 경우에는 이 방법이 통하지 않는다.

중앙로에 놓인 $k$가지 종류의 시설 $n$개가 주어질 때, 각 종류에서 가장 가까운 시설까지의 거리 중 최댓값을 가장 작게 만드는 집의 위치를 찾는 프로그램을 작성하라. 중앙로에 있는 건물의 위치는 $-1000000000$ 이상 $1000000000$ 이하의 정수로 나타내고, 위치 번호가 작을수록 서쪽에 있다. 두 건물 사이의 거리는 두 위치 번호의 차이다. 같은 위치에 시설이 둘 이상 있을 수 있고, $k$가지 종류마다 시설이 적어도 하나씩 있다. 모든 정수 위치에는 빌릴 수 있는 빈집이 적어도 하나 있다.

첫 줄에 정수 $k$와 $n$이 주어진다 ($1 \le k \le 100000$, $k \le n \le 1000000$). $k$는 시설 종류의 수, $n$은 중앙로에 있는 시설의 수다.

다음 $n$개 줄에는 시설마다 위치와 종류가 정수 두 개로 주어진다. 첫 번째 정수는 $-1000000000$ 이상 $1000000000$ 이하인 중앙로 위의 위치이고, 두 번째 정수는 $1$ 이상 $k$ 이하인 종류다.

집을 빌리기에 가장 좋은 위치를 정수 하나로 한 줄에 출력한다. 가장 좋은 위치가 둘 이상이면 그중 가장 작은 위치 번호를 출력한다.