$ Jury Compromise $

---

---

$ solution: $

这道题很有意思，它的状态设得很...奇怪。但是它的数据范围实在是太暴露了。虽然当时还是想了好久好久。首先出题人设了几个限制（两个的总和差值最小）（然后需要让它的总和最大）。我们发现每一个人的顺序是无关紧要的，这其实又提示了我们可以背包。但我们发现很难设状态，我们需要让我们的总差值接近0，但是我们在加人的时候我们的总差值可能会增大也可能会减小，导致后效性的产生，所以我们不能将总差值设为我们背包的权值。于是一个奇妙的想法产生了，我们将这个总差值直接设为状态，而将两者的总和作为权值。这样我们的权值在加入人之后必然增加，没有后效性。

然后就是记录方案了，这个大多数书上都有再设立一个数组记录转移路径的方法。但是这样的题博主推销用有向图存方案（好吧，碍于知识产权，这里留一下创立者：winlere），我们对于每一次更新都新建一个当前状态的子节点，然后连向转来的状态。这样很清晰明了，路径不易被覆盖。（具体详见代码）

---

---

$ code: $

#include<iostream>

#include<cstdio>

#include<iomanip>

#include<algorithm>

#include<cstring>

#include<cstdlib>

#include<ctime>

#include<cmath>

#include<vector>

#include<queue>

#include<map>

#include<set>

#define ll long long

#define db double

#define inf 0x7fffffff

#define rg register int

using namespace std;

int t,tt,n,m,ans,a1,a2;

int a[205];

int b[205];

int f[23][1005];

struct su{

	int da,to;

}s[5000005];

int tou[23][1005];

inline int qr(){

	register char ch; register bool sign=0; rg res=0;

	while(!isdigit(ch=getchar())) if(ch=='-')sign=1;

	while(isdigit(ch)) res=res*10+(ch^48),ch=getchar();

	return sign?-res:res;

}

inline void print(int i){

	if(i)print(s[i].to),printf(" %d",s[i].da);

}

int main(){

	//freopen(".in","r",stdin);

	//freopen(".out","w",stdout);

	while((n=qr())&&(m=qr())){ ++t; tt=0;

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

			a[i]=qr(),b[i]=qr();

		for(rg i=0;i<=20;++i)

			for(rg j=0;j<=800;++j)

				f[i][j]=-1e9,tou[i][j]=0;

		f[0][400]=0;

		for(rg k=1;k<=n;++k){

			rg x=a[k]-b[k],y=a[k]+b[k];

			for(rg i=m-1;i>=0;--i)

				for(rg j=1;j<=800;++j)

					if(f[i][j]>=0&&f[i][j]+y>f[i+1][j+x]){

						f[i+1][j+x]=f[i][j]+y;

						s[++tt].da=k; s[tt].to=tou[i][j];

						tou[i+1][j+x]=tt;

					}

		}

		for(rg i=0;i<=400;++i)

			if(f[m][400+i]>=0||f[m][400-i]>=0)

			    {ans=f[m][400+i]>f[m][400-i]?i:-i;break;}

		a1=(f[m][400+ans]+ans)>>1; a2=f[m][400+ans]-a1;

		printf("Jury #%d \nBest jury has value %d for prosecution and value %d for defence:\n",t,a1,a2);

		print(tou[m][400+ans]); puts(""); puts("");

	}

	return 0;

}