#include <bits/stdc++.h>

using namespace std; 

const long long max_size = 3e5 + 20;

int v[max_size], fr[21][21], ans, sum;
vector <int> coolnum[21][21];

void bkt (int alese, int k, int p)
{
    if (alese == k - 1)
    {
        int req = (p - (sum % p)) % p;
        if (fr[p][req] + 1 <= coolnum[p][req].size())
        {
            ans = max(ans, sum + coolnum[p][req][fr[p][req]]);
        }
        return;
    }
    for (int i = 0; i < p; i++)
    {
        if (fr[p][i] < coolnum[p][i].size())
        {
            sum += coolnum[p][i][fr[p][i]];
            fr[p][i]++;
            bkt(alese + 1, k, p);
            fr[p][i]--;
            sum -= coolnum[p][i][fr[p][i]];
        }
    }
}

void solve ()
{
    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
    {
        cin >> v[i];
    }
    sort(v + 1, v + n + 1);
    for (int i = n; i > 0; i--)
    {
        for (int j = 2; j <= 20; j++)
        {
            int r = v[i] % j;
            if (coolnum[j][r].size() < 5)
            {
                coolnum[j][r].push_back(v[i]);
            }
        }
    }
    while (q--)
    {
        int k, p;
        cin >> k >> p;
        ans = -1;
        bkt(0, k, p);
        cout << ans << "\n";
    }
}

signed main() 
{ 
#ifdef LOCAL 
    freopen("test.in", "r", stdin); 
    freopen("test.out", "w", stdout);
#else
    freopen("tricouri.in", "r", stdin);
    freopen("tricouri.out", "w", stdout);
#endif // LOCAL 
    ios_base::sync_with_stdio(false); 
    cin.tie(0); 
    cout.tie(0); 
    long long tt; 
    tt = 1;
    //cin >> tt;
    while (tt--)
    {
        solve();
    }
    return 0; 
}