<?php
fscanf(STDIN,"%d\n",$T);
while($T--)
{
$str = trim(fgets(STDIN));
$str = explode(" ",$str);
$N = intval($str[0]);
$P = intval($str[1]);
$x = array();
$y = array();
while($N--)
{
$str = trim(fgets(STDIN));
$str = explode(" ",$str);
$x[] = intval($str[0]);
$y[] = intval($str[1]);
}
$k = array();
for($i=0;$i<=count($x);$i++)
{
for($j=0;$j<=$P;$j++)
{
if($i===0 || $j ===0)
$k[$i][$j]=0;
else if($y[$i-1]<=$j)
{
$a = $x[$i-1]+$k[$i-1][$j-$y[$i-1]];
$k[$i][$j]=($a>$k[$i-1][$j])?$a:$k[$i-1][$j];
}
else
$k[$i][$j] = $k[$i-1][$j];
}
}
print($k[count($x)][$P]."\n");
 
}
 
?>

PD9waHAKZnNjYW5mKFNURElOLCIlZFxuIiwkVCk7CndoaWxlKCRULS0pCnsKJHN0ciA9IHRyaW0oZmdldHMoU1RESU4pKTsKJHN0ciA9IGV4cGxvZGUoIiAiLCRzdHIpOwokTiA9IGludHZhbCgkc3RyWzBdKTsKJFAgPSBpbnR2YWwoJHN0clsxXSk7CiR4ID0gYXJyYXkoKTsKJHkgPSBhcnJheSgpOwp3aGlsZSgkTi0tKQp7CiRzdHIgPSB0cmltKGZnZXRzKFNURElOKSk7CiRzdHIgPSBleHBsb2RlKCIgIiwkc3RyKTsKJHhbXSA9IGludHZhbCgkc3RyWzBdKTsKJHlbXSA9IGludHZhbCgkc3RyWzFdKTsKfQokayA9IGFycmF5KCk7CmZvcigkaT0wOyRpPD1jb3VudCgkeCk7JGkrKykKewpmb3IoJGo9MDskajw9JFA7JGorKykKewppZigkaT09PTAgfHwgJGogPT09MCkKJGtbJGldWyRqXT0wOwplbHNlIGlmKCR5WyRpLTFdPD0kaikKewokYSA9ICR4WyRpLTFdKyRrWyRpLTFdWyRqLSR5WyRpLTFdXTsKJGtbJGldWyRqXT0oJGE+JGtbJGktMV1bJGpdKT8kYToka1skaS0xXVskal07Cn0KZWxzZQoka1skaV1bJGpdID0gJGtbJGktMV1bJGpdOwp9Cn0KcHJpbnQoJGtbY291bnQoJHgpXVskUF0uIlxuIik7Cgp9Cgo/Pg==

MgoyIDUwCjgwIDQwCjYwIDIwCjUgMTAwCjEwMCA0MAo0MCA1MAo1MCA0MAo2MCAyMAoxMDAgNDA=

2
2 50
80 40
60 20
5 100
100 40
40 50
50 40
60 20
100 40