#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
const int MAXN = 10010;
double dp[MAXN];
double v[MAXN];
int w[MAXN];
int main() {
    int T;
    while (cin >> T) {
        while (T--) {
            memset(dp, 0, sizeof(dp));
            double m;
            int n;
            cin >> m >> n;
            int sum = 0;
            for (int i = 1; i <= n; i++) {
                cin >> w[i] >> v[i];
                sum += w[i];
            }
            dp[0] = 1;
            for (int i = 1; i <= n; i++)
                for (int j = sum; j >= w[i]; j--)
                    dp[j] = max(dp[j], dp[j - w[i]] * (1 - v[i]));

            for (int i = sum; i >= 0; i--) {
                if (dp[i] > (1 - m)) {
                    cout << i << endl;
                    break;
                }
            }
        }
    }
    return 0;
}