Description
Jeff正在玩一种卡牌游戏,在这个游戏中,每个回合玩家可以执行以下两种操作无数次:
1.使用一张手上的牌。
2.命令场上的一只生物对敌方造成伤害,每一只生物在一个回合内最多攻击一次。
现在Jeff的场上拥有n只生物,第i只怪物拥有ai点攻击力与bi点血量。
同时,Jeff手上有m张手牌。由于他的运气实在太差了,他的所有手牌都只有一个功能——使场上一只生物的攻击力等于它的血量。
现在正是斩杀对手的关键回合,Jeff希望他能通过一种合理的策略,对敌方造成最高的伤害。请帮助Jeff计算他能造成的最高伤害。
Input
题目包含多组测试数据。
第一行是一个整数T,表示有T组测试数据。
对于每组测试数据,第一行包含两个整数n,m(0 <= n,m <= 500),表示场上生物数量和手牌数量。
接下来的n行,每行包含两个整数ai,bi(1 <= ai,bi <= 10000000),表示第i只怪物的攻击力和血量。
Output
输出Jeff在一个回合内能对敌方造成的最高伤害。
Sample Input
1 3 2 1 3 2 4 5 3
Sample Output
12
Hint
对于第一组样例: Jeff可以先对场上第1只和第2只生物使用手牌,使得它们的攻击力变成3和4。 然后Jeff命令所有生物攻击,总共可以造成12点伤害。
欢迎━(*`∀´*)ノ亻!
debug
#include <iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;
int t,n,m;
long long a[1000],b[1000],c[1000],sum;
int main()
{ scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m);
sum=0;
for(int i=1;i<=n;i++){
scanf("%lld%lld",&a[i],&b[i]);
c[i]=b[i]-a[i];
sum+=a[i];
}
sort(c+1,c+n+1);
for(int i=n;i>=n-m+1&&i>=1;i--){
if(c[i]>0)
sum+=c[i];
}
cout << sum << endl;
}
return 0;
}