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

[GESP202412 七级] 武器购买

[GESP202412 七级] 武器购买

题目描述

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

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

输入格式

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

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

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

输出格式

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

样例 #1

样例输入 #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

样例输出 #1

3
-1
-1

数据范围

子任务编号 数据点占比 nn pip_i cic_i PP QQ
1 20% ≤10≤ 10 =1= 1 =1= 1 ≤10≤ 10
2 ≤100≤ 100 ≤5×104≤ 5 \times 10^4 ≤5×104≤ 5 \times 10^4
3 60% ≤5×104≤ 5 \times 10^4
  • 对于全部数据,保证有 1≤t≤101 ≤ t ≤ 10,1≤n≤1001 ≤ n ≤ 100,1≤pi,ci,P,Q≤5×1041 ≤ p_i, c_i, P, Q ≤ 5 \times 10^4。