#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;

using uint = unsigned int;
using ll   = long long;
using ull  = unsigned long long;
using ld   = long double;

#if 0
#define int  ll
#define uint ull
#endif

/**
 * Problem: Energii
 * URL: https://infoarena.ro/problema/energii
 * TL: 50 ms
 * ML: 64 MB
 *
 * Good Luck!
*/
inline void init() {
    int n;
    cin >> n;
    int k;
    cin >> k;
    vector<int> eg(n + 1), cg(n + 1);
    for (int i = 1; i <= n; i++) { cin >> eg[i] >> cg[i]; }

    vector<vector<int>> dp(n + 1, vector<int>(15001, 10000001));
    for (int i = 0; i <= n; i++) { dp[i][0] = 0; }
    for (int i = 1; i <= n; i++) {
        for (int j = eg[i]; j <= 5001; j++) {
            dp[i][j] = min(dp[i][j], dp[i - 1][j - eg[i]] + cg[i]);
        }
    }

    int minn = *min_element(dp[n].begin() + k, dp[n].end());
    if (minn == 10000001) {
        cout << "-1\n";
        return;
    }
    cout << minn << '\n';
}
inline void tc() {}

#define FIO  1
#define FILE "energii"

signed main() {
#if FIO
    freopen(FILE ".in", "r", stdin);
    freopen(FILE ".out", "w", stdout);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    init();
    int tt;
    if (!(cin >> tt)) return 0;
    while (tt--) tc();
    return 0;
}