Problem Description

小鑫是個商人，當(dāng)然商人最希望的就是多賺錢，小鑫也一樣。
這天，他來到了一個遙遠的國度。那里有著n件商品，對于第i件商品需要付出ci的價錢才能得到。當(dāng)然，對于第i件商品，小鑫在自己心中有一個估價pi：代表著當(dāng)他買下這件商品后帶回他的國家可以賣出的價格。小鑫只能帶回m件商品，你能幫他計算一下他最多能賺多少錢么？

Input

輸入有多組，到文件結(jié)束。（注：數(shù)據(jù)有很多組，請用高效率算法） 對于每一組數(shù)據(jù)。第一行是n，m。m≤n≤10000000。 緊接著有n行，每一行有兩個數(shù) c ，p。第i行代表著ci，pi。ci≤pi 數(shù)據(jù)都在int范圍內(nèi) 。 ?

Output

對于每組輸入數(shù)據(jù)只輸出一行一個數(shù)，代表小鑫能賺多少錢。

Example Input

4 2 1 2 1 3 2 2 3 4

Example Output

3

#include<stdio.h>
int a[10000001];
void q(int a[],int l,int r)//快速排序從大到小；
{
? ? int b=a[l],i=l,j=r;
? ? if(i>=j) return;
? ? while(i<j)
? ? {
? ? ? ? while(i<j&&a[j]<=b) j--;
? ? ? ? a[i]=a[j];
? ? ? ? while(i<j&&a[i]>=b)
? ? ? ? ? ? i++;
? ? ? ? a[j]=a[i];
? ? }
? ? a[i]=b;
? ? q(a,i+1,r);
? ? q(a,l,i-1);
}
int main()
{
? ? int i,j,k,n,m,p,s,c;
? ? ? ? while(~scanf("%d%d",&n,&m))
? ? ? ? {
? ? ? ? ? ? for(i=0;i<n;i++)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? scanf("%d%d",&c,&p);
? ? ? ? ? ? ? ? a[i]=p-c;
? ? ? ? ? ? }
? ? ? ? ? ? q(a,0,n-1);//利率的排序；
? ? ? ? ? ? s=0;
? ? ? ? ? ? for(i=0;i<m;i++)
? ? ? ? ? ? ? ? s+=a[i];
? ? ? ? ? ? printf("%d\n",s);
? ? ? ? }
}

總結(jié)

以上是生活随笔為你收集整理的商人小鑫的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。