选课的烦恼(pains.pas)
描述
小明打算本科毕业后申请出国,不过他想申请一个好学校,所有课程的加权平均分必须达到90分及以上。
现在小明已经修完所有的必修课,他想通过修一些选修课让课程加权平均分最终达到他的要求。一共有m门选修课可以随意选修,且他能很明确知道选修每个选修课能得到的分数,请问至少修多少门课才能达到他的要求?假设共有k门课程,其总的加权平均分的计算方法如下:
加权平均分=(成绩1*学分1+成绩2*学分2+……成绩k*学分k) / (学分1+学分2+……学分k)
输入格式(pains.in)
第一行包含一个正整数T,表示有T组测试数据。
每个测试数据第一行包含空格隔开的两个正整数n和m,表示小明已修完了n门必修课,还有m门选修课可供选择。
接下来有n行,每行包含空格隔开的一个实数ai和一个整数bi,分别表示小明第i门课的成绩以及第i门课的学分数
接下来有m行,每行包含空格隔开的一个实数cj和一个整数dj,分别表示小明第j门选修课可以获得的预期分数以及第j门选修课的学分数。
其中:
1<=T<=100, 1 <= n,m <= 100, 0 <= ai, cj <= 100, 1 <= bi, dj <= 5,所有的分数小数点后至多两位。
输出格式(pains.out)
每组测试数据输出一行,如果可以达到要求,则输出一个整数k,表示小明至少要修的选修课数目,如果小明修完所有的选修课都不可能达到要求,则输出 Impossible
输入样例
2
3 4
80.00 1
40.00 2
20.00 2
90.00 3
88.00 2
92.00 2
100.00 1
3 4
62.00 1
70.00 1
80.00 1
99.00 2
100.00 2
100.00 2
100.00 2
输出样例
Impossible
3