#1204. [GESP202412 七级] 武器购买

[GESP202412 七级] 武器购买

题目描述

商店里有 nn 个武器,第 ii 个武器的强度为 pip_i,花费为 cic_i。

小杨想要购买一些武器,满足这些武器的总强度不小于 PP,总花费不超过 QQ,小杨想知道是否存在满足条件的购买方案,如果有,最少花费又是多少。

输入格式

第一行包含一个正整数 tt,代表测试数据组数。

对于每组测试数据,第一行包含三个正整数 n,P,Qn,P,Q,含义如题面所示。

之后 nn 行,每行包含两个正整数 pi,cip_i,c_i,代表武器的强度和花费。

输出格式

对于每组测试数据,如果存在满足条件的购买方案,输出最少花费,否则输出 -1。

样例

3
3 2 3
1 2
1 2
2 3
3 3 4
1 2
1 2
2 3
3 1000 1000
1 2
1 2
2 3
3
-1
-1

题目来源:洛谷 P11377