题目5--N盒点心

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

有N盒点心,这些盒子标号为1,2,...N,你有一次机会选择一些盒子作为你的晚餐,但是每个盒子里的点心的数量是未知的,不过有人告诉你一些信息:
①这些盒子里的点心总和是C个;
②对于盒子i,其中的点心个数最少的有low_i个,最多有high_i个,即low_i <= box_i <= high_i,box_i是第i盒的点心个数。
你选择的方式如下,一次挑出N盒中的若干盒,也就是{1,2,...N}的一个子集,然后拿走你选出的盒子,再打开它们,到此时你才知道你到底获得了多少个点心。为了吃饱晚餐,你需要吃X个点心,请问你至少需要选多少盒点心才能保证一定吃饱?
例如样例中:第一组选第3,4,5三盒第二组选第1,3两盒。 

Input

 多组测试数据,第一行一个整数T,表示测试数据数量,1 <= T <= 5
每组测试数据有相同的结构组成:
每组数据的第一行三个整数N,C,X,表示盒子个数、点心总数、需要的点心个数,其中1 <= N <= 50, 1 <= X <= C;
之后的N行,每行2个整数low_i,其中1 <= low_i <= high_i <= 10^7 ,同时保证SUM{low_i|1 <= i <= N} <= C <= SUM{high_i|1 <= i <= N},即数据确保点心总数与点心上下界的合法性;

Output

 每组数据一行输出,即最少需要挑的盒子数量。

Sample Input

2
5 15 12
1 1
2 2
3 3
4 4
5 5
3 60 8
5 49
2 48
3 47

Sample Output

3
2

Hint

 

Source