Description

Format

Input

从文件equation.in读入数据。

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

Output

向文件equation.out输出数据。
文件仅一行，包含一个整数，表示方程的整数解的个数。

Sample 1

Input

5
150
1 4
1 4
1 3
-1 4
-1 4

Output

502

Limitation

1s, 128MiB for each test case.