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;
}