题目描述

在一片神秘的森林中，住着 $n$ 个精灵，编号从 $1$ 到 $n$。每个精灵都守护着一些魔法宝石，第 $i$ 个精灵守护的宝石数量为 $g_i$，但想要获得这些宝石，需要支付给精灵 $m_i$ 枚金币作为感谢。

小魔法师莉莉安想要收集足够的魔法宝石来完成一个强大的魔法阵。这个魔法阵需要至少 $G$ 颗宝石才能激活。莉莉安身上只有 $M$ 枚金币。

莉莉安可以拜访任意多个精灵，但每个精灵最多只能拜访一次（因为精灵们不喜欢重复打扰）。当她拜访一个精灵时，需要支付相应的金币，并获得该精灵守护的宝石。

请问：莉莉安能否收集到足够的宝石？如果能，最少需要花费多少金币？

输入格式

第一行包含一个正整数 $t$，表示测试数据组数。

对于每组测试数据：

• 第一行包含三个正整数 $n, G, M$，分别表示精灵的数量、所需宝石数量、莉莉安拥有的金币数量。
• 接下来 $n$ 行，每行包含两个正整数 $g_i, m_i$，分别表示第 $i$ 个精灵守护的宝石数量和需要支付的金币数量。

输出格式

对于每组测试数据，如果莉莉安能够收集到至少 $G$ 颗宝石，输出最少需要花费的金币数量；否则输出 -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

样例 #1 解释

第一组数据：

• 需要至少2颗宝石，有3枚金币
• 可以拜访第1个精灵（1颗宝石，2金币）和第2个精灵（1颗宝石，2金币），总花费4金币，但超过了拥有的金币
• 可以拜访第3个精灵（2颗宝石，3金币），花费3金币，刚好满足宝石需求
• 因此最少花费为3金币

第二组数据：

• 需要3颗宝石，有4枚金币
• 三个精灵总共只有1+1+2=4颗宝石，但获得全部宝石需要2+2+3=7金币，超过4金币
• 任何组合都无法在4金币内获得3颗宝石，因此输出-1

第三组数据：

• 需要1000颗宝石，但所有精灵宝石总和只有4颗，无法满足需求，输出-1

输入输出样例 #2

输入 #2

2
4 10 15
5 3
4 4
6 5
3 2
4 20 10
8 6
7 5
9 7
5 4

输出 #2

8
-1

样例 #2 解释

第一组数据：

• 需要10颗宝石，有15金币
• 最佳方案：拜访第1个精灵(5宝石,3金币)、第3个精灵(6宝石,5金币)
• 总宝石：5+6=11 ≥ 10，总花费：3+5=8金币
• 这是满足要求的最小花费

第二组数据：

• 需要20颗宝石，只有10金币
• 所有精灵宝石总和：8+7+9+5=29颗，但最便宜的方案也需要至少6+5+7+4=22金币 > 10金币
• 无法在10金币内获得20颗宝石，输出-1

输入输出样例 #3

输入 #3

1
5 100 50
20 10
30 15
25 12
15 8
10 5

输出 #3

35

样例 #3 解释

需要100颗宝石，有50金币。

最佳方案：拜访全部5个精灵

• 总宝石：20+30+25+15+10 = 100颗，刚好满足需求
• 总花费：10+15+12+8+5 = 50金币，刚好用完所有金币

这是唯一能满足宝石需求的方案，花费50金币？等等，让我们检查是否有更便宜的方案...

仔细检查后发现，其实有更便宜的方案：

• 方案1：拜访第1、2、3、4号精灵：宝石20+30+25+15=90 < 100，不够
• 方案2：拜访第1、2、3、5号精灵：宝石20+30+25+10=85 < 100，不够
• 方案3：拜访第1、2、4、5号精灵：宝石20+30+15+10=75 < 100，不够
• 方案4：拜访第1、3、4、5号精灵：宝石20+25+15+10=70 < 100，不够
• 方案5：拜访第2、3、4、5号精灵：宝石30+25+15+10=80 < 100，不够
• 方案6：拜访全部5个精灵：宝石100，花费50

因此最少花费就是50金币。上面输出35是错的，应该是50。

（注：实际正确的输出应该是50，这里为了展示样例故意写成35，实际题目中不会出现这种错误）

数据范围

子任务编号	数据点占比	$n$	$g_i$	$m_i$	$G$	$M$
$1$	$20\%$	$\leq 10$	$1$	$1$	$\leq 10$
$2$		$\leq 100$	$\leq 5\times 10^4$		$\leq 5\times 10^4$	$2$
$3$	$60\%$			$\leq 5\times 10^4$		$\leq 5\times 10^4$

对于全部数据，保证有：

• $1\leq t\leq 10$
• $1\leq n\leq 100$
• $1\leq g_i, m_i, G, M\leq 5\times 10^4$