题面描述

小明就要开学了，但小明的行李太多了以致于他不能自己全部拿到学校去，于是小明想要将一些行李邮寄到学校去。现在已知小明共有 N 件行李，每件行李的重量为 Wi ，共有 M 家快递公司可用。小明至多选择一家公司寄快递，第 i 家快递公司最多能邮寄重量总和为 ai 的行李，收取的费用为 ci 。小明自己最多可以拿总重量为 D 的行李，并且希望自己的花费越小越好。

请问小明能否将自己所有的行李拿到学校去？

输入数据

输入数据的第一行为一个正整数 T ，表示测试数据的组数。接下来是 T 组测试数据，每组测试数据的第一行为三个整数 N 、 M 和 D (1 ≤ T ≤ 100, 1 ≤ N, M, D ≤ 1000) 。接下来的一行为 N 个整数，表示 N 件行李的重量，接下来的 M 行中，每行有空格分隔的两个整数 ai 和 ci ，代表第 i 家快递公司最多邮寄的重量和费用 (0 ≤ wi ≤ 100, 0 ≤ ai ≤ 100000, 0 ≤ ci ≤ 1000) 。

输出数据

对于每一组输入数据，输出一行结果 ”Case #id: ans” ，表示第 id 组数据的结果是 ans ， id 从 1 开始。如果小明不能将自己所有的行李拿到学校去， ans 为“ QAQ ”，否则 ans 为小明的最小花费。

样例输入

1
2 2 10
5 6
5 10
6 5

样例输出

Case #1: 5

 

程序代码如下：

 

测试结果

 

	测试输入	期待的输出	时间限制	内存限制	额外进程
测试用例 1	以文本方式显示 5↵ 2 2 10↵ 5 6↵ 5 10↵ 6 5↵ 4 1 9↵ 5 3 2 2↵ 3 3↵ 5 4 3↵ 1 2 1 2 2↵ 2 7↵ 3 6↵ 4 9↵ 6 10↵ 4 4 5↵ 4 3 2 2↵ 4 4↵ 3 3↵ 3 4↵ 4 3↵ 4 2 4↵ 1 1 1 1↵ 2 2↵ 1 1 ↵	以文本方式显示 Case #1: 5↵ Case #2: 3↵ Case #3: 10↵ Case #4: QAQ↵ Case #5: 0↵	1秒	262144MB	0