2015
07-16

# Assassin’s Creed

Ezio Auditore is a great master as an assassin. Now he has prowled in the enemies’ base successfully. He finds that the only weapon he can use is his cuff sword and the sword has durability m. There are n enemies he wants to kill and killing each enemy needs Ai durability. Every time Ezio kills an enemy he can use the enemy’s sword to kill any other Bi enemies without wasting his cuff sword’s durability. Then the enemy’s sword will break. As a master, Ezio always want to do things perfectly. He decides to kill as many enemies as he can using the minimum durability cost.

The first line contains an integer T, the number of test cases.
For each test case:
The first line contains two integers, above mentioned n and m (1<=n<=10^5, 1<=m<=10^9).
Next n lines, each line contains two integers Ai, Bi. (0<=Ai<=10^9, 0<=Bi<=10).

The first line contains an integer T, the number of test cases.
For each test case:
The first line contains two integers, above mentioned n and m (1<=n<=10^5, 1<=m<=10^9).
Next n lines, each line contains two integers Ai, Bi. (0<=Ai<=10^9, 0<=Bi<=10).

2
3 5
4 1
5 1
7 7
2 1
2 2
4 0

Case 1: 3 4
Case 2: 0 0

/*

贪心。
1、所有人都没有菜刀、无法砍别人。对于这种情况，直接根据cost排序，

2、存在有菜刀的人：
如果猪角的武器的耐久、不足以使他杀死“有菜刀、且cost最小”的人，那

(1)所有的人的菜刀可以杀死的人的总和sum+1>=n（因为至少一个人必须是

(2)上述sum+1<n，那么去除猪角已经砍死的那个人，然后根据cost排序，直

(1)和(2)的最优为第二组ans；

比较第一、二组ans，最优既为所求。
至于2.(2)，为什么可以直接先干掉cost最大的sum个人呢？根据菜刀可杀人

2013-06-27
*/

#include"iostream"
#include"cstdio"
#include"queue"
#include"cstring"
#include"algorithm"
using namespace std;
const int N=100005;

int n,m,cnt1,cnt2;
int ans1,ans2,ret1,ret2,zz[N];
struct node{
int cost,val;
}E[N];
int cmp(node n1,node n2){
return n1.cost<n2.cost;
}

void solve1()
{
int i;
ans1=0;
ret1=m;
for(i=0;i<n;i++)
{
if(E[i].val)	continue;
if(ret1>=E[i].cost)	{ans1++;ret1-=E[i].cost;}
else	break;
}
}
void solve2()
{
int i;
ans2=0;
ret2=m;
for(i=0;i<n;i++)	if(E[i].val)	break;
if(i>=n)			return ;
if(ret2<E[i].cost)	return ;

int flag=i;
int sum=0;
for(i=0;i<n;i++)	sum+=E[i].val;
if(sum+1>=n)	{ans2=n;ret2=m-E[flag].cost;return ;}

ans2=sum+1;
ret2-=E[flag].cost;
memset(zz,0,sizeof(zz));
zz[flag]=1;
i=n-1;
while(sum>0)
{
if(!zz[i])	{zz[i]=1;sum--;}
i--;
}
for(i=0;i<n;i++)
{
if(zz[i])	continue;
if(ret2<E[i].cost)	break;
ans2++;
ret2-=E[i].cost;
}
}
int main()
{
int T,Case;
int i;
cin>>T;
for(Case=1;Case<=T;Case++)
{
scanf("%d%d",&n,&m);
for(i=0;i<n;i++)	scanf("%d%d",&E[i].cost,&E[i].val);

sort(E,E+n,cmp);
solve1();
solve2();
if(ans1>ans2 || (ans1==ans2 && ret1>ret2))
printf("Case %d: %d %d\n",Case,ans1,m-ret1);
else	printf("Case %d: %d %d\n",Case,ans2,m-ret2);
}
return 0;
}