Description：

有 $N$ 个商品，第 $i$ 个商品价格为 $P_i$ 。有 $K$ 张优惠券，使用优惠券购买第 $i$ 个商品价格会降为 $C_i$ 。求花不超过 $M$ 的钱最多可以买多少奶牛？

$1\le n \le 50000$

Solution：

先用优惠券买 $C$ 前 $K$ 小的牛，在最小堆中加入 $P-C$ 代表可以用这么多价值获得一张优惠券，剩下的牛按 $P$ 升序排序，如果 $P-C>q.top()$ ，即如果把它用优惠券买能省下更多的钱，那就取出堆顶并把 $P-C$ 放到堆里，如果不能就用原价买，因为用优惠券会亏，不断重复直到超过 $m$ 。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cstring>

using namespace std;

int n,k;

#define MAXN 50010

long long m;

struct obj

{

	int p,c;

}s[MAXN];

bool cmp_p_from_low_to_high(obj a,obj b){return a.p < b.p;}

bool cmp_c_from_low_to_high(obj a,obj b){return a.c < b.c;}

priority_queue<int,vector<int>,greater<int> > q;

int main()

{

	scanf("%d%d%lld",&n,&k,&m);

	for(int i = 1;i <= n;++i)

		scanf("%d%d",&s[i].p,&s[i].c);

	sort(s + 1,s + 1 + n,cmp_c_from_low_to_high);

	long long sum = 0;

	for(int i = 1;i <= k;++i)

	{

		if(sum + s[i].c > m)

		{

			cout << i - 1 << endl;

			return 0;

		}

		sum += s[i].c;

		q.push(s[i].p - s[i].c);

	}

	if(k == n)

	{

		cout << n << endl;

		return 0;

	}

	sort(s + k + 1,s + 1 + n,cmp_p_from_low_to_high);

	for(int i = k + 1;i <= n;++i)

	{

		if(s[i].p - s[i].c > q.top())

		{

			sum += q.top();

			q.pop();

			sum += s[i].c;

			q.push(s[i].p - s[i].c);

		}

		else

		{

			sum += s[i].p;

		}

		if(sum > m)

		{

			cout << i - 1 << endl;

			return 0;

		}

	}

	cout << n << endl;

	return 0;

}