시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB297413416.585%

문제

문제를 풀지 못하면 꿈나라로 가지 못하는 한별이는 오늘도 어려운 문제들을 쓰러트리기 위해 드롭킥을 연습한다.

드롭킥은 체공시간이 길수록 위력이 강해지기 때문에, 한별이는 자신이 가진 $M$의 점프력을 이용하여 드롭킥의 체공시간을 최대화시키고자 한다.

한별이가 사는 세상은 놀랍게도 $y=0$이 지면인 $2$차원 평면으로 표현할 수 있다. 한별이는 자신의 집의 위치인 $(0,0)$에서 위로 뛰어올라서 $(0,M)$에 도달한 후, $1$초에 $1$씩 지면을 향해 떨어진다. 떨어지는 동안 한별이는 $1$초에 $1$씩 왼쪽과 오른쪽 중 원하는 방향으로 이동할 수 있다.

한별이의 집 주위에는 $N$ 개의 $x=x_i$ 형태의 상승기류가 존재한다. $i$ 번째 상승기류는 $x$좌표 $x_i$와 세기 $p_i$를 가지고 있으며, 한별이가 체공 중에 $x$좌표 $x_i$에 도달하면 한별이는 $p_i$만큼 상승하고 $i$ 번째 기류는 사라진다.

한별이가 지면에 떨어질 때까지 걸리는 시간의 최댓값을 구하시오. 한별이가 상승기류를 만나는 동시에 높이가 $0$이 되면 한별이가 지면에 떨어진 것으로 간주한다. 또한 같은 위치에 $2$개 이상의 상승기류는 존재하지 않고, 한별이의 집에 상승기류가 존재하지 않음이 보장된다.

입력

첫 번째 줄에 상승기류의 개수 $N$과 한별이의 점프력 $M$이 주어진다. ($0 \le N \le 5\,000$, $1 \le M \le 10^9$)

두 번째 줄부터 $N+1$번째 줄까지 상승기류의 $x$좌표 $x_i$와 상승기류의 세기 $p_i$가 주어진다. ($-10^9 \le x_i \le 10^9$, $x_i \neq 0$, $1 \le p_i \le 10^9$)

출력

첫 번째 줄에 한별이가 지면에 떨어질 때까지 걸리는 최대 시간을 초 단위로 출력한다.

예제 입력 1

2 3
2 5
-4 7

예제 출력 1

8

출처

Contest > BOJ User Contest > 아니메컵 > 아니메컵 2쿨 E번