선물 퍼즐

페이만의 생일 파티가 열리고 있다. 오랜 친구 케이반은 생일 선물로 퍼즐 하나를 샀다. 퍼즐은 가로 길이 $l$, 세로 길이 $w$인 평평한 직사각형 보드와 실 한 가닥으로 이루어져 있다. 보드에는 위쪽 가장자리로부터 서로 다른 거리에 길이 $l$인 가로 레일이 $n$개 놓여 있다. 각 레일에는 레일 위를 자유롭게 미끄러질 수 있는 장애물이 하나씩 있다. 그림에 보드의 예가 나와 있다. 레일은 점선으로, 장애물은 굵은 선분으로 표시되어 있다.

퍼즐을 풀려면 실로 보드의 왼쪽 위 모서리와 오른쪽 아래 모서리를 연결해야 한다. 실은 보드 안에 있어야 하며 장애물을 통과할 수 없다. 그림에는 퍼즐을 푸는 방법 하나가 나와 있다. 케이반은 페이만이 어려운 퍼즐을 잘 푼다고 믿기 때문에, 두 모서리를 연결할 수 있는 가장 짧은 실을 페이만에게 주고 싶어 한다. 케이반을 도와 그 실의 길이를 구하라.

첫 줄에 세 정수 $l$, $w$, $n$이 주어진다. $l$은 보드의 가로 길이, $w$는 세로 길이, $n$은 레일의 개수이다. 조건은 $2 \le l, w \le 10^9$이고 $1 \le n \le \min(100\,000, w-1)$이다.

이어지는 $n$개의 줄에는 정수 $y_i$와 $l_i$가 주어진다. $y_i$는 $i$번째 레일과 보드 위쪽 변 사이의 거리이고, $l_i$는 $i$번째 레일 위 장애물의 길이이다. 조건은 $1 \le y_i \le w-1$이고 $1 \le l_i \le l-1$이다. 모든 $y_i$는 서로 다르다. 장애물과 실의 폭은 0으로 본다.

장애물을 배치하여 길이 $t$의 실로 왼쪽 위 모서리와 오른쪽 아래 모서리를 장애물을 피해 연결할 수 있을 때, $t$의 최솟값을 한 줄에 출력한다. 상대 오차가 $10^{-9}$ 이하이면 정답으로 인정한다.