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

1. 我對油畫沒啥了解阿，不過其實朱耷也做過，如果僅以這幅畫來說我同意你的觀點，而如果說到未來水墨畫的可能性我覺得這種結合應該是一種方式，而如何結合偏向何種方向的結合就不知道了，畢竟不到那個水平是無法思考的（笑）

2. 有预感这下无聊图会变成老阿訇讲经堂，阿訇们从珍藏经书中截出很正常的片段，然后讲一波经，既是原创，也受群众欢迎，美滋滋。

3. 有预感这下无聊图会变成老阿訇讲经堂，阿訇们从珍藏经书中截出很正常的片段，然后讲一波经，既是原创，也受群众欢迎，美滋滋。

4. 有预感这下无聊图会变成老阿訇讲经堂，阿訇们从珍藏经书中截出很正常的片段，然后讲一波经，既是原创，也受群众欢迎，美滋滋。

5. 有预感这下无聊图会变成老阿訇讲经堂，阿訇们从珍藏经书中截出很正常的片段，然后讲一波经，既是原创，也受群众欢迎，美滋滋。

6. 有预感这下无聊图会变成老阿訇讲经堂，阿訇们从珍藏经书中截出很正常的片段，然后讲一波经，既是原创，也受群众欢迎，美滋滋。