Description

已知一个 $n$ 元高次方程：

其中：$x_1$,$x_2$,···,$x_n$是未知数，$k_1$,$k_2$,···,$k_n$是系数，$p_1$,$p_2$,···,$p_n$是指数。且方程中的所有数均为整数。 假设未知数 $x_i \in [1,m] \space ( i \in [1,n])$，求这个方程的整数解的个数。

Format

Input

文件的第1行包含一个整数n。第2行包含一个整数M。第3行到第n+2行，每行包含两个整数，分别表示$k_i$和$p_i$。两个整数之间用一个空格隔开。第3行的数据对应i=1，第n+2行的数据对应i=n。

Output

文件仅一行，包含一个整数，表示方程的整数解的个数。

Samples

3
150
1  2
-1  2
1  2

178

Limitation

对于 $100\%$ 的数据，$1\le n \le 6$，$1\le m \le 150$，且

答案不超过 $2^{31}-1$，$p_i \in \mathbb N^*$。