基础 $dp$ ，考虑 $dp[i][j]$ 表示前 $i$ 个选择出 $j$ 个的最小代价。

$T$ 了几发，改成一维过的，可能 $stl$ 太耗时了。改成一维就和优化 $01$ 背包一样。

#include <bits/stdc++.h>

using i64 = long long;

constexpr int N = 1E3 + 10;

i64 dp[4 * N];

void solve() {
    int n, k;
    std::cin >> n >> k;

    for (int i = 1; i <= k; ++i) {
        dp[i] = 1E18;
    }

    int f[5] {};
    for (int i = 1; i <= n; ++i) {
        std::cin >> f[1] >> f[2] >> f[3] >> f[4];

        for (int j = std::min(4 * i, k); j >= 0; --j) {
            for (int l = 1; l < 5; ++l) {
                if (j - l >= 0) {
                    dp[j] = std::min(dp[j], dp[j - l] + f[l]);
                }
            }
        }
    }
    std::cout << dp[k] << "\n";
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t;
    std::cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}