题目描述
小杨整理出 组互相独立的询问。每组给出 件物品，第 件重 、价值 ，要求选出的物品总重量恰好等于 ，求最大总价值；无解输出 。请逐组回答。
输入格式
第一行一个整数 。
对于每组：第一行两个整数 ；接下来 行，每行两个整数 。
输出格式
每组一行，一个整数（无解 ）。
样例
输入 1
3
3 8
2 3
3 4
4 5
3 100
2 3
3 4
4 5
3 5
2 3
3 4
4 5
输出 1
-1
-1
7
三组物品相同：重量恰好 与 都凑不出（子集和只有 ），恰好 可由第 1、2 件组成，价值 。
数据范围
，，，。