• 状态定义：$f[i][j]$ 表示前 $i$ 次机会恰好获得 $j$ 颗星星；
• 初始化：$f_{i,j}=inf, f_{0,0}=0$；
• 转移方程：每个物品可选可不选

$$f_{i,j} = \min_{k\in[0,4]} \{ f_{i-1, j-k} + a_{i,k} \} $$

• 目标：$f_{n,m}$。

#include <cstring>
#include <iostream>
#include <map>
#include <set>
#include <string>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N = 1e3 + 1, M = 4e3 + 1, INF = 0x3f3f3f3f, B = 131;
int n, m, a[N][5];
int f[N][M];
// f[i][j] :前 i 次机会恰好获得 j 颗星星.

void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= 4; j++)
            cin >> a[i][j];

    memset(f, 0x3f, sizeof f);
    f[0][0] = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= m; j++) {
            int& t = f[i][j];
            for (int k = 0; k <= 4 && j >= k; k++)
               t = min(t, f[i - 1][j - k] + a[i][k]);
        }
    cout << f[n][m] << endl;
}
int main(int argc, char* argv[]) {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int T; cin >> T; while (T--) solve();
    return 0;
}