新题么。略水。
就一个序列，如果起点单增的话只要终点单增就不会冲突。
然后最少单增子序列覆盖=最长不降子序。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long dint;
#define _l (long long int)
const int maxn = 100009;
int n, m, a[maxn], t[maxn], s;
dint v[maxn], v0[maxn];
int btQry(int p) {
int s = 0;
for (; p; p -= (p & -p))
s = max(s, t[p]);
return s;
}
void btChg(int p, int v) {
for (; p <= n; p += (p & -p))
t[p] = max(t[p], v);
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
scanf("%d%d", &n, &m);
for (int i = 0; i < n; ++ i) {
int p, s;
scanf("%d%d", &p, &s);
v0[i] = p + _l s * m;
v[i] = v0[i];
}
sort(v, v + n);
memset(t, 0, sizeof(t));
for (int i = 0; i < n; ++ i) {
int a = n - (lower_bound(v, v + n, v0[i]) - v);
int f = btQry(a) + 1;
btChg(a, f);
}
printf("%d\n", btQry(n));
}