农夫约翰想给他的 N 头奶牛购买礼物，但是他的预算只有 B 元。
奶牛 ii 希望获得的礼物的价格为 Pi，运输成本为 Si，也就是说约翰要帮奶牛 i 买礼物，共需花费 Pi+Si 元钱。
约翰有一张特殊的优惠券，如果使用该优惠券来订购一份礼物，那么该礼物的价格会变为只有正常价格的一半。
如果约翰用该优惠券给奶牛 i 买礼物，那么他只需要支付 ?Pi/2?+Si 元钱。
请帮助约翰确定他最多可以给多少头奶牛购买礼物。
输入格式
第一行包含两个整数 N 和 B。
接下来 N 行，每行包含两个整数 Pi 和 Si。
输出格式
输出约翰可以购买礼物的奶牛最大数量。
数据范围
1≤N≤1000,
1≤B≤109,
0≤Pi,Si≤109
输入样例：
5 24
4 2
2 0
8 1
6 3
12 5
输出样例：
4
样例解释
一种最佳方案是约翰给前 44 头奶牛购买礼物，在给第 33 头奶牛购买礼物时使用优惠券。
花费为 (4+2)+(2+0)+(4+1)+(6+3)=22(4+2)+(2+0)+(4+1)+(6+3)=22。
分析：贪心+枚举
代码如下：
#include <bits/stdc++.h>
using namespace std;
struct node{
long long p,s;
}a[1010];
int n,b;
int ans;
bool cmp(node x,node y)
{
return x.p+x.s<y.p+y.s;
}
int main()
{
cin>>n>>b;
for(int i=1;i<=n;i++)cin>>a[i].p>>a[i].s;
sort(a+1,a+1+n,cmp);
for(int i=1;i<=n;i++)
{
//cout<<a[i].p<<" "<<a[i].s<<endl;
long long sum=a[i].p/2+a[i].s;
int num=1;
if(sum>b) continue;
for(int j=1;j<=n;j++)
{
if(j==i)continue;
//if(i==1)cout<<sum<<" ";
sum+=(a[j].p+a[j].s);
if(sum>b) break;
num++;
}
//cout<<i<<" "<<sum<<" "<<num<<endl;
ans=max(num,ans);
}
cout<<ans;
return 0;
}
?
