武器购买

题目描述

商店⾥有 个武器，第 个武器的强度为 ，花费为 。 ⼩杨想要购买⼀些武器，满⾜这些武器的总强度不⼩于 ，总花费不超过 ，⼩杨想知道是否存在满⾜条件的购买 ⽅案，如果有，最少花费⼜是多少。

输入格式

第⼀⾏包含⼀个正整数 ，代表测试数据组数。 对于每组测试数据，第⼀⾏包含三个正整数 ，含义如题⾯所⽰。 之后 ⾏，每⾏包含两个正整数 ，代表武器的强度和花费。

输出格式

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

样例输入 #1

1 3
2 3 2 3
3 1 2
4 1 2
5 2 3
6 3 3 4
7 1 2
8 1 2
9 2 3
10 3 1000 1000
11 1 2
12 1 2
13 2 3
1 3
2 -1
3 -1
子任务编号 数据点占比
1 20%
2 20%
3 60%

样例输出 #1

数据范围

见题目描述

知识点与难度

本题涉及的知识点从属于 GESP 7级，难度等级：⭐⭐⭐⭐⭐⭐ 。

测试点分布

生测试数据后，按实际 subtask 分组改写上表。