2446. sunny购物

单点时限: 2.0 sec

内存限制: 256 MB

sunny 要去超市买东西,每一个物品都有相应的价格 cost,但同时也能获得一定数量的附赠券 lottery,附赠卷积累到一定数量之后可以参加超市抽奖 :).sunny 现在手中已经有了一定数量的附赠券,再需要 K 张他就能参加抽奖了。sunny 想在一次集齐 K 张奖券,但是又不想买贵的东西,他不在乎一共花了多少钱,只在乎最贵的东西的价格。

现在给出超市中 N 个商品的价格和附赠券的数量,让你帮 sunny 确定一个购买商品的最优方案。使得获得附赠券的总数至少为 K, 但是价格最高的的商品的价格尽量低。

输入格式

第一行有一个整数 T, 表示测试数据的总数,每组测试数据第一行有两个整数 N(1<=N<=1000),K(1<=K<=10000), 接下来有 N 行。每行两个整数 cost,value(1<=cost,value<=1000)

输出格式

每组测试数据输出一行 . 如果能够满足奖券的数目,则输出最优方案中价格最高的商品的价格 , 如果无论如何也不能满足奖券的数目,则输出 “UNLUCKY”(不带引号)

样例

Input
3
2 45
14 20
48 19
4 21
18 5
11 7
6 10
11 16
4 21
18 8
35 20
15 11
13 15
Output
UNLUCKY
11
15

81 人解决,112 人已尝试。

91 份提交通过,共有 164 份提交。

3.2 EMB 奖励。

创建: 11 年,1 月前.

修改: 2 年,4 月前.

最后提交: 1 月前.

来源: 2008年选拔赛

题目标签