文件目录

// 01背包
/* 总体：有n个物品，购买总花费m，总强度过关的方案
 * 状态：dp[i][j] 对于前i个物品，总花费为j时，总强度过关的方案
 * 方程：对于第i件物品，买或不买
 *  dp[i][j]=max(dp[i-1][j-ci]+pi,dp[i-1][j])
 * 边界：0
 * 次序，左到右
 */
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        int n, P, q, p[105] = {}, c[105] = {};
        cin >> n >> P >> q;
        for (int i = 1; i <= n; i++)
            cin >> p[i] >> c[i];
        int dp[105][50005] = {};
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= q; j++)
            {
                dp[i][j] = dp[i - 1][j];
                if (j >= c[i])
                    dp[i][j] = max(dp[i][j], dp[i - 1][j - c[i]] + p[i]);
            }
        int ans = -1;
        for (int i = 1; i <= q; i++)
            if (dp[n][i] >= P)
            {
                ans = i;
                break;
            }
        cout << ans << endl;
    }
    return 0;
}