폭죽

일차원 직선 위의 좌표 $0$과 좌표 $D$에 각각 폭죽 발사대가 있다. 좌표 $0$의 발사대는 오른쪽으로, 좌표 $D$의 발사대는 왼쪽으로 폭죽을 발사한다. 두 폭죽은 모두 $1$초에 거리 $1$만큼 이동한다. 편의상, 폭죽이 발사되는 시각을 $0$초라고 하자.

두 발사 장치의 사이에는 장치 $N$ 개가 있다. 각 장치에 폭죽이 들어가면 해당 장치에 설정된 시간만큼 폭죽이 장치 안에 잡혀 있다가 다시 이동을 시작한다.

두 폭죽이 만나면 즉시 폭발한다. 폭죽이 폭발하는 시각을 계산하는 프로그램을 작성하라. 폭죽이 장치의 위치에서 폭발할 수도 있음에 유의하라.

위 그림은 $D=13$이고 $N=4$인 경우를 보여준다. 그림은 위에서 아래로 시간 순서이며, 그림에서 $t$는 시각을 의미한다. 좌표 $2$, $5$, $8$, $11$에 장치가 있으며, 각 장치에 설정된 시간은 맨 왼쪽 장치부터 $2$, $2$, $2$, $1$이다.

왼쪽에서 발사된 폭죽은 $2$초에 맨 왼쪽 장치에 도착한다. $2$초의 지연 시간이 지난 $4$초에 맨 왼쪽 장치를 떠난다. 비슷하게, $7$초에 왼쪽에서 두 번째 장치에 도착하고, $9$초에 떠난다. 이 폭죽은 $10$초에 좌표 $6$을 지난다.

오른쪽에서 발사된 폭죽은 $2$초에 맨 오른쪽 장치에 도착하고, $3$초에 떠난다. 오른쪽에서 두 번째 장치에 $6$초에 도착하고, $8$초에 떠난다. 이 폭죽도 $10$초에 좌표 $6$을 지난다. 따라서, 이 경우의 답은 $10$이다.

입력 형식

첫 줄에 장치의 개수를 나타내는 정수 $N$과 폭죽 발사 위치를 나타내는 정수 $D$가 공백으로 구분되어 주어진다. ($0 \le N \le 500\,000$; $0 < D \le 1\,000\,000\,000$)

이어지는 $N$ 개의 줄의 $i$ 번째 줄에는 $i$ 번째 장치가 위치한 좌표를 나타내는 정수 $X_i$와 그 장치에 설정된 시간을 나타내는 정수 $T_i$가 공백으로 구분되어 주어진다. ($0 < X_1 < X_2 < \cdots < X_N < D$; $1 \le T_i \le 2\,000$)

출력 형식

첫 줄에 폭죽이 폭발하는 시각을 소수점 첫째 자리까지 출력한다.

예제 1

4 13
2 2
5 2
8 2
11 1

10.0

예제 2

0 5

2.5

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞혀야 그 종류에 배정된 점수를 받을 수 있다.

해설