题目背景

放暑假了，zjy 想去旅游。

题目描述

zjy 的暑假一共有 $k$ 天，而 Deepseek 提供了 $n$ 个景点，每个景点需要旅游 $a_i$ 天，快乐值会增加 $b_i$，请你帮他算算快乐值最大是多少。zjy 不会重复去一个景点。

输入格式

第一行输入一个数 $T$，表示数据组数。

接下来每组数据第一行输入 $2$ 个数 $n$ 和 $k$。

下面 $n$ 行，每行输入 $2$ 个数 $a_i$ 和 $b_i$。

输出格式

输出 $T$ 行，每行输出每组数据的最大快乐值。

输入输出样例 #1

输入 #1

3
1 2
1 3
3 4
2 5
3 3
4 1
5 10
3 4
7 7
2 5
4 1
5 3

输出 #1

3
5
12

说明/提示

$1 \leq n,k \leq 1000$

$1 \leq a_i,b_i \leq 10^{5}$

$1 \leq T \leq 100$