Farmer John's N cows (1 <= N <= 100,000) are out exercising their hooves again, jogging along an infinite track. Each cow starts at a distinct position, and some cows run at different speeds.

The track is divided into lanes so that cows may move past each other. No two cows in the same lane may ever occupy the same position. Farmer John doesn't want any cow to have to change lanes or adjust speed, and he wonders how many lanes he will need if the cows are going to run for T minutes (1 <= T <= 1,000,000,000).

Line 1: N and T.

Lines 2..1+N: Each contains the initial position and speed of a single cow (both at most 1 billion). All cows start at distinct positions, given in increasing order.

A single integer indicating the minimum number of lanes necessary so that no two cows in the same lane ever occupy the same location (including at time T).

riseoj 작성

출처 올림피아드 > USACO > 2014-2015 > December > Gold