3866: 盈利计划问题
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：4
解决：2
题目描述
某公司有 n 名员工，他们可以参与各种项目来创造利润。共有 m 种不同的项目可供选择，第 i 种项目能产生 profit[i] 的利润，但需要 group[i] 名员工共同参与。
每个员工最多只能参与一个项目，如果参与了某个项目就不能参与其他项目。一个项目的子集被称为"盈利计划"，当且仅当该子集能够产生至少 minProfit 的总利润，且参与项目的员工总数不超过 n。
请问一共有多少种不同的盈利计划可以选择？由于答案可能很大，请输出结果对 10^9 + 7 取模的值。
输入
第一行包含三个整数 n, minProfit, m，分别表示员工总数、最低利润要求和项目总数。
接下来 m 行，每行包含两个整数 group[i] 和 profit[i]，表示第 i 个项目的员工需求和产生的利润。
输出
输出一个整数，表示盈利计划的总数对 10^9 + 7 取模的结果。
样例输入 复制
10 5 3
2 6
3 7
5 8
样例输出 复制
7提示
1 ≤ n ≤ 100
0 ≤ minProfit ≤ 100
1 ≤ m ≤ 100
1 ≤ group[i] ≤ 100
0 ≤ profit[i] ≤ 100