레이팅 미적용설명
무더운 여름날, 소 베시는 몹시 게으름을 피우고 싶다. 베시는 짧은 거리만 이동해도 최대한 많은 맛있는 풀에 닿을 수 있는 위치에 자리 잡으려고 한다.
베시의 들판에는 N개의 풀밭(1 <= N <= 100,000)이 있으며, 들판은 긴 1차원 수직선으로 생각할 수 있다. i번째 풀밭에는 g_i 단위의 풀(1 <= g_i <= 10,000)이 있고, 들판 위의 서로 다른 점 x_i(0 <= x_i <= 1,000,000)에 위치한다. 베시는 들판의 한 점(풀밭과 같은 점이어도 된다)을 초기 위치로 골라, 그 위치로부터 거리 K걸음(1 <= K <= 2,000,000) 이내에 있는 풀의 양이 최대가 되게 하려고 한다.
베시가 가능한 최선의 초기 위치를 고른다면 닿을 수 있는 풀의 최대량을 구하는 것을 도와라.
제약
입력 형식
첫째 줄: 두 정수 N과 K가 주어진다.
둘째 줄부터 1+N째 줄까지: i+1째 줄에는 i번째 풀밭을 나타내는 두 정수 g_i와 x_i가 주어진다.
출력 형식
베시의 최적 위치로부터 거리 K 이내에 있는 풀의 최대량을 출력한다.
Standard input / output
This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:
입력을 읽을 파일
lazy.in · 출력을 쓸 파일 lazy.out예제 1
입력
4 3
4 7
10 15
2 2
5 1출력
11설명
Output details: Bessie should locate herself at position x=4, reaching the grass at x=1, x=2, and x=7.
문제 정보
태그