‹ 上一题下一题 ›

s02203. 方程的解数未做

1000 ms 256 MB 测试点 10 S-14·搜索进阶 S·算法自拟题 S-14 深度优先搜索广度优先搜索记忆化搜索搜索的剪枝优化双向广度优先搜索迭代加深搜索

文件读写输入s02203.in输出s02203.out

题目描述

求方程 $\sum_{i = 1}^{n} k_{i} x_{i}^{p_{i}} = 0$ 的解的组数，其中每个 $x_{i}$ 都取 $1 \sim m$ 之间的整数，系数 $k_{i}$ 与指数 $p_{i}$ 已给出。

输入格式

第一行两个整数 $n, m$ 。接下来 $n$ 行，每行两个整数 $k_{i}, p_{i}$ 。

输出格式

一行一个整数，解的组数。

样例

输入

2 3
1 1
-1 1

输出

数据范围

对于 30% 的数据： $n \leq 3$
对于 60% 的数据： $n \leq 4$
对于 100% 的数据： $n \leq 6$ ， $m \leq 150$ ， $∣ k_{i} ∣ \leq 100$ ， $1 \leq p_{i} \leq 4$

输入

输出

答案