往届 ACM 队训练题 (参考)

1105. 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
不限期开放

题目列表