题目描述

今天辰辰又要采药了，他带了一个容量为 $V$ 的背包。他来到山上，发现这座山上的草药比较特别，体积不是 $1$ 就是 $2$，当然价值有所不同。现在他想知道如何采药，能使他今天的收获最大。

格式

输入格式

第一行为正整数 $t(≤5)$，表示数据组数；每组数据中，第一行为正整数 $n(≤ 10^5)$ 和 $V(≤2×10^5)$，分别表示草药的总数和背包容量；接下来 $n$ 行，每行两个正整数 $x_i(x_i=1$ 或 $2)$ 和 $v_i(≤10^4)$，分别表示每株草药的体积和价值。

输出格式

对于每组数据，输出辰辰选取的草药的最大价值。

样例1

输入样例1

1
3 2 
1 2
2 7
1 3

输出样例1

7

来源

地址：芜湖市二十七中电脑班刷题课
作者：汪老师
模拟赛$T3$

文件IO

freopen("medicine.in","r",stdin);
freopen("medicine.out","w",stdout);