题目描述

有一趟列车有 $M+1$ 个车站，从 $0$ 到 $M$ 编号。有 $N$ 种商品，第 $i$ 种只在编号 $[l_i,r_i]$ 的车站出售。一辆列车有一个预设好的系数 $d$，从 $0$ 出发，只会在 $d$ 的倍数车站停车。对于 $d$ 从 $1$ 到 $M$ 的列车，求最多能买到多少种商品。

输入格式

第一行输入 $N$ $M$

接下来 $N$ 行每行两个整数 $l_i$ $r_i$

输出格式

输出一个整数代表答案

3 3
1 2
2 3
3 3

3
2
2

7 9
1 7
5 9
5 7
5 9
1 1
6 8
3 4

7
6
6
5
4
5
5
3
2

提示

数据范围

• $1\le N\le 3\times 10^{5}$
• $1\le M\le 10^{5}$
• $1\le l_i\le r_i\le M$