#include <fstream>

using namespace std;

#define max(a,b) ((a) > (b) ? (a) : (b))
#define min(a,b) ((a) < (b) ? (a) : (b))

const int NMAX = 300000;

ifstream fin("tricouri.in");
ofstream fout("tricouri.out");
int N,M,t[NMAX];
long long T[6][21];

void calc()
{
        long long aux[6][21];
        for(int i = 0; i < N; ++i)
        {
                memset(aux,0,sizeof aux);

                for(int j = 1; j < min(i + 2,6); ++j)

                        for(int k = 1; k < 21; ++k)
                         for(int l = 1; l < 21; ++l)
                        
                          if( (T[j - 1][k] + t[i]) % l == 0 )
                           aux[j][l] = max( aux[j][l],max(T[j][k],T[j - 1][k] + t[i]) );

                memcpy(T,aux,sizeof T);
        }
}

int main()
{
        fin>>N>>M;
        for(int i = 0; i < N; ++i)
                fin>>t[i];

        calc();

        int x,y;
        while(M--)
        {
                fin>>x>>y;
                fout<<(T[x][y] ? T[x][y] : -1)<<'\n';
        }

        return 0;
}