UOJ Logo

NOI.AC

1S 512MB

#1603. 西虹市的工厂

Statistics

西虹市的一间工厂里有$n$个工人。工厂可以生产$m$件产品,每个产品需要$x[i]$个工人,这件产品的利润是$y[i]$元。厂长想要生产的产品的利润和不低于$P$元,并且生产这些产品的需要工人数量不能超过$n$。一共有多少种方案?注意每件产品只能被生产一次,每个工人至多只能参与一个产品的生产。

数据输入

第一行是三个数字$n$,$m$和$P$,含义如上。

接下来$m$行,每行两个数字$x[i]$和$y[i]$,分别表示该件产品需要的工人数量和利润。

数据输出

一个数字,表示满足条件的方案数。答案对$10^9 + 7$取模。

样例输入1

5 2 3

2 2

2 3

样例输出1

2

样例解释1

可以选择生产第一件产品或者第二件产品,均满足条件。

样例输入2

10 3 5

2 6

3 7

5 8

样例输出2

7

样例解释

可以选择的生产方案是:(1), (2), (3), (1,2), (1,3), (2,3), and (1,2,3),一共7种。

范围说明

对于60%的数据有:$1leq n, m, P, x[i], y[i] leq 100$。

对于100%的数据有:$1leq n, m, P, x[i] leq 100, 1leq y[i] leq 10^9$