let rec range a b = if a >= b then Seq.empty else fun () -> Seq.Cons (a, range (a+1) b)

let n = Scanf.scanf "%d" Fun.id
let vw = List.init n (fun _ -> Scanf.scanf " %d %d" (fun v w -> v, w))
let varr = List.to_seq vw |> Seq.map fst |> Array.of_seq
let warr = List.to_seq vw |> Seq.map snd |> Array.of_seq

let rec items arr x =
  if x = 1 then [arr.(0)]
  else arr.(x-1) :: items arr (x / 2)

let enumerate t lim va wa =
  let ve = Array.make (1 lsl t) 0 in
  let we = Array.make (1 lsl t) 0 in
  range 0 (1 lsl t) |> Seq.iter (fun b ->
    let ws = range 0 t |> Seq.fold_left (fun ws i ->
      if b land (1 lsl i) > 0 then ws + wa.(i) else ws) 0 in
    if ws <= lim then (
      let vs = range 0 t |> Seq.fold_left (fun vs i ->
        if b land (1 lsl i) > 0 then vs + va.(i) else vs) 0 in
      we.(b) <- ws;
      ve.(b) <- vs;
  ));
  (ve, we)

let solve x l =
  let module A = Array in
  let vs = A.of_list @@ items varr x in
  let ws = A.of_list @@ items warr x in
  let t = A.length vs in

  let lvs = A.sub vs 0 (t/2) in
  let rvs = A.sub vs (t/2) (t-t/2) in
  let lws = A.sub ws 0 (t/2) in
  let rws = A.sub ws (t/2) (t-t/2) in

  let ve1, we1 = enumerate (t/2) l lvs lws in
  let ve2, we2 = enumerate (t-t/2) l rvs rws in

  let ans = ref 0 in
  for i = 0 to (1 lsl (t/2)) - 1 do
    let v1 = ve1.(i) in
    let w1 = we1.(i) in
    for j = 0 to (1 lsl (t-t/2)) - 1 do
      let v2 = ve2.(j) in
      let w2 = we2.(j) in
      if w1 + w2 <= l then
        ans := max !ans (v1 + v2);
    done;
  done;
  !ans

let () =
  Scanf.scanf " %d" @@ fun q ->
  for i = 1 to q do
    Scanf.scanf " %d %d" solve
    |> Printf.printf "%d\n"
  done
