2323 - 【j基础】方程的解数

周周在求解一个 nn 元的高次方程:

k1x1p1+k2x2p2++knxnpn=0\displaystyle k_1x_1^{p_1}+k_2x_2^{p_2}+\ldots+k_nx_n^{p_n}=0

其中:x1,x2,,xnx_1,x_2,\ldots,x_n 是未知数,k1,k2,,knk_1,k_2,\ldots,k_n 是系数,p1,p2,,pnp_1,p_2,\ldots,p_n 是指数。方程中所有数都一定是整数。

假设未知数 1xiM,i=1n1\leq x_i\leq M,i=1 \ldots n。你能帮周周算出这个方程的整数解个数吗?

Input

第一行输入一个整数 n(1n4)n(1 \leq n \leq 4)

第二行输入一个整数 M(1M150)M(1 \leq M \leq 150)

33 行到第 n+2n+2 行,每行输入两个整数,分别表示 ki(ki20)k_i(|k_i| \leq 20)pi(1pi4)p_i(1 \leq p_i \leq 4)。两个整数之间用一个空格隔开。

Output

输出一行,输出一个整数,表示方程的整数解的个数。

Examples

Input
复制

3
100
1 2
-1 2
1 2

Output
复制

104

Hint

这里我们依然采用暴力的思想,枚举每一个 xx 所有可能的值, 然后进行判断是否计算结果为 00

Time Limit 1 second
Memory Limit 128 MB
Discuss Stats
上一题 下一题