아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

소 조깅

면접 대비

시간 제한1초메모리 제한256 MB

요약
T분 동안 앞지르기가 금지될 때 최종 위치가 같은 소 무리가 몇 개인지 셉니다.
난이도

보통10점 중 5점

유형
그리디, 배열
정답자
아직 제출이 없습니다

문제

소들이 또 발굽을 단련하러 나섰다. 무한히 긴 1차선 트랙에서 소 NN마리가 조깅한다 (1≤N≤100 0001 \le N \le 100\,000). 소들의 출발 위치는 모두 다르고, 달리는 속도가 서로 다른 소도 있다.

트랙이 1차선뿐이라 소는 앞의 소를 앞지르지 못한다. 빠른 소가 앞의 소를 따라잡으면 부딪히지 않도록 속도를 줄이고, 그 소와 같은 무리가 된다.

소들은 TT분 동안 달린다 (1≤T≤1091 \le T \le 10^9). TT분이 지난 뒤 무리가 몇 개 남는지 구하라. TT분이 끝나는 시점에 위치가 같은 두 소는 같은 무리로 센다.

입력

첫 줄에 두 정수 NN과 TT가 주어진다.

다음 NN개의 줄에는 소 한 마리의 출발 위치와 속도가 주어진다. 위치는 0 이상의 정수, 속도는 양의 정수이고 둘 다 10억 이하이다. 모든 소의 출발 위치는 서로 다르며, 위치가 증가하는 순서로 주어진다.

출력

TT분이 지난 뒤 남아 있는 무리의 개수를 정수 하나로 출력한다.

예제4

  1. 예제 1

    입력
    5 3
    0 1
    1 2
    2 3
    3 2
    6 1
    
    예상 출력
    3
    
  2. 예제 2

    입력
    1 1000000000
    0 1000000000
    
    예상 출력
    1
    
  3. 예제 3

    입력
    4 1000000000
    0 5
    1 5
    2 5
    3 5
    
    예상 출력
    4
    
  4. 예제 4

    입력
    3 1000000000
    0 3
    1 2
    2 1
    
    예상 출력
    1