나무와 그림자 easy

시간 제한2초메모리 제한1024 MB

요약
서로 다른 위치에 심어진 나무들의 위치와 높이, 그리고 고정된 태양 각도가 주어질 때 나무 위에 지는 그림자 길이의 합을 구한다.
난이도

보통10점 중 6점

유형
정렬, 스택, 누적 합
정답자
아직 제출이 없습니다

문제

하늘이는 xx축과 평행한 수직선 모양의 땅에 나무 NN그루를 심었다. 나무가 심어져 있는 위치는 모두 다르며, 나무의 두께는 무시할 수 있을만큼 얇다.

나무가 잘 자라기 위해서는 햇빛을 많이 받는 것이 중요하기 때문에, 하늘이는 각 나무에 그림자가 얼마나 지고 있는 지 알아보기로 했다.

태양은 현재 서쪽에 떠있고 햇빛이 지면과 기울기 −t-t를 이루며 평행하게 비추고 있다.

그림은 t=2t=2일 때의 상황을 나타낸다. 오른쪽 나무 위에 생기는 그림자의 길이는 44이다.

하늘이를 위해 각 나무 위에 생기는 그림자의 길이의 합을 구해주자. 모든 그림자를 합하는 것이 아닌 나무 위에 생기는 그림자만 합하는 것에 주의하자.

입력

첫째 줄에 NN과 정수 tt가 공백을 사이에 두고 주어진다. (1≤N≤300,000;(1\le N\le 300\\, 000; 1≤t≤1,000)1\le t\le 1\\, 000)

둘째 줄부터 NN개의 줄에 걸쳐 각 나무가 심어진 위치와 높이를 의미하는 두 정수 x_ix\_i, h_ih\_i가 공백을 사이에 두고 주어진다. (−109≤x_i≤109;(-10^9\le x\_i\le 10^9; 1≤h_i≤109)1\le h\_i\le 10^9)

출력

첫째 줄에 나무 위에 생기는 그림자의 길이 합을 나타내는 정수를 출력한다.

예제1

  1. 예제 1

    입력
    3 2
    5 10
    7 4
    2 8
    
    예상 출력
    6