#3403. 陪审团 暂未评定

时间限制:1000 ms 内存限制:256 MiB 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: root

题目描述

在一个遥远的国家,一名嫌疑犯是否有罪需要由陪审团来决定。

陪审团是由法官从公民中挑选的。

法官先随机挑选N个人(编号1,2…,N)作为陪审团的候选人,然后再从这N个人中按照下列方法选出M人组成陪审团。

首先,参与诉讼的控方和辩方会给所有候选人打分,分值在0到20之间。

第 i 个人的得分分别记为p[i]和d[i]。

为了公平起见,法官选出的M个人必须满足:辩方总分D和控方总分P的差的绝对值|D-P|最小。

如果选择方法不唯一,那么再从中选择辨控双方总分之和D+P最大的方案。

求最终的陪审团获得的辩方总分D、控方总分P,以及陪审团人选的编号。

输入格式

输入包含多组测试数据。

每组测试数据第一行包含两个整数N和M。

接下来N行,每行包含两个整数p[i]和d[i]。

每组测试数据之间隔一个空行。

当输入数据N=0,M=0时,表示结束输入,该数据无需处理。

输出格式

对于每组数据,第一行输出’Jury #C’,C为数据编号,从1开始。

第二行输出“Best jury has value P for prosecution and value D for defence:”,P为控方总分,D为辩方总分。

第三行输出按升序排列的陪审人选编号,每个编号前输出一个空格。

每组数据输出完后,输出一个空行。

样例

样例输入

4 2
1 2
2 3
4 1
6 2
0 0

样例输出

Jury #1
Best jury has value 6 for prosecution and value 4 for defence:
 2 3

数据范围与提示

,

POJ 1015