#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

void solve() {
    int N;
    long long K;
    cin >> N >> K;

    // {傾き(限界価値), その個数} を管理するマップ
    map<long long, long long> mp;
    long long total_count = 0; // 現在マップに入っている要素の総数
    long long profit = 0;      // 確定した純利益

    for (int i = 0; i < N; ++i) {
        long long A, B, C, D;
        cin >> A >> B >> C >> D;

        // 1. ジュエルを買う
        if (B > 0) {
            mp[-A] += B;
            total_count += B;
        }

        // 2. ジュエルを売る
        long long count_to_add = 0;
        while (D > 0 && !mp.empty()) {
            // 最も価値の高い（傾きが最大の）ジュエルを取得
            auto it = prev(mp.end());
            long long s = it->first;
            long long cnt = it->second;

            // 利益が出ないならこれ以上売らない
            if (s <= -C) break;

            long long use = min(D, cnt);
            profit += use * (s + C);
            count_to_add += use;
            D -= use;

            // マップの更新（使い切った要素は削除）
            if (use == cnt) {
                mp.erase(it);
            } else {
                it->second -= use;
            }
        }
        
        // 売却のキャンセル権（傾き -C）を追加
        if (count_to_add > 0) {
            mp[-C] += count_to_add;
        }

        // 3. 保管庫の容量制限 (K個まで)
        while (total_count > K) {
            // 最も価値の低い（傾きが最小の）ジュエルから捨てる
            auto it = mp.begin();
            if (it->second <= total_count - K) {
                total_count -= it->second;
                mp.erase(it);
            } else {
                it->second -= (total_count - K);
                total_count = K;
            }
        }
    }

    cout << profit << "\n";
}

int main() {
    // 高速な入出力
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int T;
    if (cin >> T) {
        while (T--) {
            solve();
        }
    }
    return 0;
}