#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = (l); i < (r); i++)
using namespace std;

typedef long long ll;

int main() {
    int N, M, maxw = 0, minv = 1e9, ans = 1e9;
    cin >> N >> M;
    vector<int> w(N), l(M), v(M), s(1 << N, 0), d(1 << N, 0), a(N);
    rep(i, 0, N) {
        cin >> w[i];
        maxw = max(maxw, w[i]);
    }
    rep(i, 0, M) {
        cin >> l[i] >> v[i];
        minv = min(minv, v[i]);
    }
    if (maxw > minv) {
        cout << -1 << endl;
        return 0;
    }
    rep(i, 0, 1 << N) {
        rep(j, 0, N) {
            if ((i >> j) & 1) s[i] += w[j];
        }
        rep(j, 0, M) {
            if (s[i] > v[j]) d[i] = max(d[i], l[j]);
        }
        //cout << i << " " << s[i] << " " << d[i] << endl;
    }
    rep(i, 0, N) a[i] = i;
    do {
        //rep(i, 0, N) cout << a[i]; cout << endl;
        vector<int> b(N + 1, 0);
        rep(i, 0, N) b[i + 1] = b[i] | (1 << a[i]);
        //rep(i, 0, N + 1) cout << b[i] << " "; cout << endl;
        vector<vector<int>> c(N, vector<int>(N));
        rep(i, 0, N - 1) {
            rep(j, i + 1, N) {
                c[i][j] = d[b[i] ^ b[j + 1]];
                //cout << "c[" << i << "][" << j << "]=" << c[i][j] << " ";
            }
        }
        vector<int> dist(N, 0);
        rep(i, 1, N) {
            rep(j, 0, i) {
                dist[i] = max(dist[i], dist[j] + c[j][i]);
            }
        }
        ans = min(ans, dist[N - 1]);
        //out << ans << endl;
    } while (next_permutation(a.begin(), a.end()));
    cout << ans << endl;
}
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
# define rep(i,a,b) for(int i=(a); i<=(b); ++i)
# define drep(i,a,b) for(int i=(a); i>=(b); --i)
typedef __int128 int_;
inline int readint(){
	int a = 0; char c = getchar(), f = 1;
	for(; c<'0'||c>'9'; c=getchar())
		if(c == '-') f = -f;
	for(; '0'<=c&&c<='9'; c=getchar())
		a = (a<<3)+(a<<1)+(c^48);
	return a*f;
}
inline void writeint(int_ x){
	if(x > 9) writeint(x/10);
	putchar((x-x/10*10)^48);
}

int_ exgcd(int_ a,int_ b,int_ &x,int_ &y){
	if(!b){ x = 1, y = 0; return a; }
	int_ d = exgcd(b,a%b,y,x);
	y -= (a/b)*x; return d;
}

int main(){
	int_ zxy, sxy;
	for(int T=readint(); T; --T){
		int_ ans = -1; // infinity
		int x = readint(), y = readint();
		int p = readint(), q = readint();
		int T1 = 2*(x+y), T2 = p+q;
		int_ lcm = exgcd(T1,T2,zxy,sxy);
		lcm = 1ll*T1/lcm*T2;
		rep(i,x,x+y-1) rep(j,p,p+q-1){
			int_ a, b, d = exgcd(T1,T2,a,b);
			if((j-i)%d) continue; // no solution
			d = (j-i)/d; a *= d, b *= d;
			int_ t = T1*a+i; // remainder
			t = (t%lcm+lcm)%lcm; // be positive
			if(ans == -1 || ans > t) ans = t;
		}
		if(ans == -1) puts("infinity");
		else writeint(ans), putchar('\n');
	}
	return 0;
}
