XTU 1262 Fish(优先队列+贪心)

钓鱼
http://202.197.224.59/exam/index.php/problem/read/id/1262
题目描述

小明很喜欢钓鱼，现在有n个池塘可以钓鱼，第i个池塘首次内能钓到ai条鱼。 第i个池塘如果被钓过k次，那么每次下一次能钓到的鱼的数目为max{0,ai−k×bi}。 现在小明能钓m次鱼，请问他最多能钓到多少条鱼？

输入

第一行是一个整数T(1≤T≤100)，表示样例的个数。
每个样例的第一行是n(1≤n≤1000),m(1≤m≤100000)；
以后的n行，每行是ai(1≤ai≤10000),bi(0≤bi≤10000)。

输出

每行输出一个样例的结果。

样例输入

2
3 5
3 1
4 2
1 0
2 5
2 1
1 1
样例输出

12
4
样例解释

第一个样例，在第1个池塘钓3次，第2个池塘钓2次，3+2+1+4+2 = 12；
第二个样例，在第1个池塘钓2次，第2个池塘钓1次，2+1+1 = 4。

思路：
维护一个优先队列，使价值最高的鱼优先级最高，钓出这种鱼后，从队首弹出这种鱼，改变价值后再压入，这样便能保证每次钓到的鱼都是价值最高的。