// ---------- begin scannner ----------
#[allow(dead_code)]
mod scanner {
    use std::str::FromStr;
    pub struct Scanner<'a> {
        it: std::str::SplitWhitespace<'a>,
    }
    impl<'a> Scanner<'a> {
        pub fn new(s: &'a String) -> Scanner<'a> {
            Scanner {
                it: s.split_whitespace(),
            }
        }
        pub fn next<T: FromStr>(&mut self) -> T {
            self.it.next().unwrap().parse::<T>().ok().unwrap()
        }
        pub fn next_bytes(&mut self) -> Vec<u8> {
            self.it.next().unwrap().bytes().collect()
        }
        pub fn next_chars(&mut self) -> Vec<char> {
            self.it.next().unwrap().chars().collect()
        }
        pub fn next_vec<T: FromStr>(&mut self, len: usize) -> Vec<T> {
            (0..len).map(|_| self.next()).collect()
        }
    }
}
// ---------- end scannner ----------

use std::io::Write;
use std::collections::*;

type Map<K, V> = BTreeMap<K, V>;
type Set<T> = BTreeSet<T>;
type Deque<T> = VecDeque<T>;

fn main() {
    use std::io::Read;
    let mut s = String::new();
    std::io::stdin().read_to_string(&mut s).unwrap();
    let mut sc = scanner::Scanner::new(&s);
    let out = std::io::stdout();
    let mut out = std::io::BufWriter::new(out.lock());
    run(&mut sc, &mut out);
}

fn run<W: Write>(sc: &mut scanner::Scanner, out: &mut std::io::BufWriter<W>) {
    let t: u32 = sc.next();
    for _ in 0..t {
        let n: usize = sc.next();
        let k: u64 = sc.next();
        let mut p = vec![(0, 0, 0); n];
        for p in p.iter_mut() {
            p.0 = sc.next::<u64>();
            p.1 = sc.next::<usize>();
            p.2 = sc.next::<u64>();
        }
        p.sort_by_key(|p| p.2);
        let mut stack = vec![vec![]; 3];
        for (c, w, f) in p {
            stack[w].push((f, c));
        }
        let find_max = |stack: &[Vec<(u64, u64)>]| -> usize {
            let mut pos = 0;
            for i in (1..3).rev() {
                if let Some(&v) = stack[i].last() {
                    if pos == 0 {
                        pos = i;
                    }
                    let p = stack[pos].last().unwrap();
                    if v.0 > p.0 {
                        pos = i;
                    }
                }
            }
            pos
        };
        let mut ans = 0;
        while stack.iter().any(|s| s.len() > 0) {
            let pos = find_max(&stack);
            let po = stack[pos].last_mut().unwrap();
            let (f, c) = *po;
            let cnt = c * pos as u64 / k;
            ans += f * cnt;
            po.1 -= cnt * k / pos as u64;
            if po.1 == 0 {
                stack[pos].pop();
                continue;
            }
            ans += po.0;
            let mut rem = k;
            while stack.iter().any(|s| s.len() > 0) && rem > 0 && !(rem == 1 && stack[1].is_empty()) {
                if rem == 1 {
                    let po = stack[1].last_mut().unwrap();
                    po.1 -= 1;
                    rem -= 1;
                    if po.1 == 0 {
                        stack[1].pop();
                    }
                    continue;
                }
                let pos = find_max(&stack);
                let po = stack[pos].last_mut().unwrap();
                let (_, c) = *po;
                let up = c.min(rem / pos as u64);
                rem -= up * pos as u64;
                po.1 -= up;
                if po.1 == 0 {
                    stack[pos].pop();
                }
            }
        }
        writeln!(out, "{}", ans).ok();
    }
}