UVA323 Jury Compromise

在遥远的国度 Frobnia，法庭的判决由一群普通公民组成的陪审团决定。每次审判开始时，都需要按以下方式选出一个陪审团：首先，从公众中随机抽取若干人。对于这个候选池中的每一个人，辩护方和控告方会分别给出一个 $0$ 到 $20$ 的评分，表示他们对这个人的偏好程度。$0$ 表示完全不喜欢，$20$ 表示认为这个人非常适合陪审团。 根据双方的评分，法官会选出陪审团。为了确保审判的公正性，陪审团对辩护方和控告方的倾向应该尽可能平衡，所以陪审团的选择必须按照双方都满意的方式。具体地，给定一个包含 $n$ 个候选人的候选池，以及每个候选人 $i$ 的两个值 $d_i$（辩护方的评分）和 $p_i$（控告方的评分），你需要从中选出 $m$ 人组成陪审团。如果 $J$ 是 $\{1,\dots,n\}$ 的一个包含 $m$ 个元素的子集，那么 $D(J)=\sum_{k\in J}d_k$ 和 $P(J)=\sum_{k\in J}p_k$ 分别表示这个陪审团对于辩护方和控告方而言的总评分。 对于最优的陪审团 $J$，$|D(J)-P(J)|$ 的值必须最小。如果有多个陪审团的 $|D(J)-P(J)|$ 相同，则应选择 $D(J)+P(J)$ 最大的那个，因为陪审团必须尽可能对双方都理想。 你需要编写一个程序，实现这个陪审团选择过程，并在给定候选人的情况下选出最优陪审团。

输入包含多组测试数据。 每一组测试数据的第一行为两个整数 $n$ 和 $m$（$1\le n\le200,1\le m\le20,m\le n$），含义见题目描述。 接下来 $n$ 行，每行包含两个整数 $p_i$ 和 $d_i$，表示控告方和辩护方对第 $i$ 个候选人的评分。相邻两组测试数据之间以一个空行分隔。输入以 $n=m=0$ 的一轮结束。

对于每组测试数据，第一行输出选择陪审团的轮次（即测试数据编号，如 `Jury #1`、`Jury #2` 等）。 接下来一行，输出陪审团的 $D(J)$ 和 $P(J)$ 值（具体格式详见样例输出），下一行按升序输出选中的 $m$ 个候选人的编号，并且你需要在每个编号前输出一个空格。同时，你需要在每组测试数据后输出一个空行。

对于 $100\%$ 的数据，$1\le n\le 200,1\le m\le 20,m\le n,0\le d_i,p_i\le 20$。