#include <fstream>
#include <algorithm>

using namespace std;

bool f(long long t[20][5][6], int i, int j, int ind)
{
    for (int i = 0; i < 6; i++)
        if (t[i][j][i] == ind)
            return false;

    return true;
}

int main()
{
    int n, q;

    ifstream in("tricouri.in");

    in >> n >> q;

    int nr[300000] = { 0 };

    for (int i = 0; i < n; i++)
    {
        in >> nr[i];
    }

    sort(nr, nr + n);

    long long m[20][5][6];

    for (int i = 0; i < 20; i++)
        for (int j = 0; j < 5; j++)
            for (int k = 0; k < 6; k++)
                m[i][j][k] = -1;

    for (int i = 0; i < 20; i++)
    {
        int ind = n - 1;
        while (nr[ind] % (i + 1) != 0 && ind >= 0)
            ind--;

        if (ind < 0)
            ;
        else
        {
            m[i][0][0] = nr[ind];
            m[i][0][1] = ind;
        }
    }

    for (int i = 0; i < 20; i++)
    {
        for (int j = 1; j < 5; j++)
        {
            for (int k = 0; k < 20; k++)
            {
                int ind = n - 1;
                while (((nr[ind] + m[k][j - 1][0]) % (i + 1) != 0 && ind >= 0) || !f(m, k, j - 1, ind))
                    ind--;

                if (ind < 0)
                    ;
                else
                {
                    if (nr[ind] + m[k][j - 1][0] > m[i][j][0])
                    {
                        m[i][j][0] = nr[ind] + m[k][j - 1][0];
                        m[i][j][j + 1] = ind;
                    }
                }
            }
        }
    }

    ofstream out("tricouri.out");

    int k, p;
    for (int i = 0; i < q; i++)
    {
        in >> k >> p;

        out << m[p - 1][k - 1][0] << '\n';
    }

    in.close();
    out.close();
}