https://codeforces.com/contest/1974/problem/E

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=a;i>=n;i--)
#define oz 998244353
#define N 200010
#define INF 0x3f3f3f3f
typedef long long ll;
#define endl '\n'
const int mod = 1e9 + 7;

int f[N]; //代表第i天获得j幸福值还能剩多少钱
int n, x;
int a[N], b[N];


void solve() {
    cin >> n >> x;

    int sum = 0;
    for (int i = 1; i <= n ; i ++) {
        cin >> a[i] >> b[i];
        sum += b[i];
    }

    for(int i = 1; i <= sum; i++)f[i] = -1e18;


    f[0] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = sum; j >= 0; j--) {
            if (j >= b[i] && f[j - b[i]] >= a[i])f[j] = max(f[j], f[j - b[i]] - a[i]); //状态转移 若当前幸福值小于b[i],且钱> a[i] 则可操作；

            f[j] += x;
        }
    }
    int res = 0;
    for (int i = 1; i <= sum; i ++)if (f[i] > 0)res = i;
    cout << res << endl;

}

signed main() {

    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int T = 1;
    cin >> T;
    while (T --)

        solve();

    return 0;
}