记录编号	159972	评测结果	AAAAAAAAAAAAAA
题目名称	奶牛跑步2	最终得分	100
用户昵称	清羽	是否通过	通过
代码语言	C++	运行时间	0.552 s
提交时间	2015-04-23 14:50:14	内存使用	1.00 MiB

//by tsingyawn
/*
贪心问题
k表示当前跑道数
pos[i]表示每个跑道上最慢的奶牛结束时的位置
end[i]表示奶牛i结束时的位置
策略：对于每个新加进来的奶牛，选择一个pos值比其end大，且最小的跑道。
小结论：从后往前扫，则如果位置较小的一个点的终止位置比位置较大的一个点
        的终止位置小，则两牛不可能相遇
*/
#include<cstdio>
#include<iostream>
#include<cstring>
#include<ctime>
#include<algorithm>
using namespace std;

typedef long long LL;

struct Node{
	Node* ch[2];
	LL s,v,r;
	
	LL cmp(LL d){
		if(d==v) return -1;
		return d<v?0:1;
	}
	Node(LL v1):v(v1) {
		ch[0]=ch[1]=NULL;
		r=rand();
	}
};

const int maxn=100050;
const LL INF=9223372036854775807;

char buf[40];
Node* root=NULL;
LL T,n,k,end[maxn];

template<class T> inline bool getd(T& x)
{
	int ch=getchar();
	bool neg=false;
	while(ch!=EOF && ch!='-' && !isdigit(ch)) ch=getchar();
	if(ch==EOF) return false;
	if(ch=='-'){
		neg=true;
		ch=getchar();
	}
	x=ch-'0';
	while(isdigit(ch=getchar())) x=x*10+ch-'0';
	if(neg) x=-x;
	return true;
}

template<class M> inline void putd(M x)
{
	int p=0;
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x==0) buf[p++]=x;
	while(x){
		buf[p++]=x%10;
		x/=10;
	}
	for(int i=p-1;i>=0;i--) putchar(buf[i]+'0');
	putchar('\n');
}

void rotate(Node* &o,LL d){
	Node* k=o->ch[d^1];o->ch[d^1]=k->ch[d];k->ch[d]=o;
	o=k;
}

void insert(Node* &o,LL x)
{
	if(o==NULL) o=new Node(x);
	else{
		LL d=x<o->v?0:1;
		insert(o->ch[d],x);
		if(o->ch[d]->r>o->r) rotate(o,d^1);
	}
}

LL find(Node* &o,LL x)
{
	if(o==NULL) return INF;
	LL d=o->cmp(x);
	if(d==1 || d==-1) return find(o->ch[1],x);
	else return min(find(o->ch[d],x),o->v);
}

void remove(Node* &o,LL x)
{
	LL d=o->cmp(x);
	if(d==-1){
		if(o->ch[0]!=NULL && o->ch[1]!=NULL){
			LL d2=o->ch[0]->r>o->ch[1]->r?0:1;
			rotate(o,d2^1);
			remove(o->ch[d2^1],x);
		}
		else{
			Node* u=o;
			if(o->ch[0]==NULL) o=o->ch[1];
			else o=o->ch[0];
			delete u;
		}
	}
	else remove(o->ch[d],x);
}

void init()
{
	getd(n);getd(T);
	for(int i=0;i<n;i++){
		LL x,v;
		getd(x);getd(v);
		end[i]=x+v*T;
	}
}

void work()
{
	k=0;
	for(int i=n-1;i>=0;i--){
		LL x=find(root,end[i]);
		if(x==INF)	k++;
		else remove(root,x);
		insert(root,end[i]);
	}
	putd(k);
}

int main()
{
	freopen("cowjogb.in","r",stdin);
	freopen("cowjogb.out","w",stdout);
	init();
	work();
	fclose(stdin);
	fclose(stdout);
	return 0;
}