#include <bits/stdc++.h>
#include <cstring>
#include <cstdio>
#pragma GCC optimize ("O3")
#define din cin
#define dout out
#define pi 3.14159265359
#define sw(x,y) x^=y,y^=x,x^=y
#define bmin(a,b)((a<b)?(a):(b))
#define bmax(a,b)((a>b)?(a):(b))
#define bminify(a,b)a=bmin(a,b)
#define bmaxify(a,b)a=bmax(a,b)
#define fto(i,ii,n)for(i=ii;i<n;i++)
#define f first
#define s second
#define mod 2000003ll
#define nmax 1<<19
#define lim 351
using namespace std;
typedef long long ll;
ifstream in("tricouri.in");
ofstream out("tricouri.out");
//FILE *fin=fopen("infasuratoare.in","r");
//FILE *fout=fopen("infasuratoare.out","w");
mt19937 e(8);
int n,i,j,k,l,x,y,m,a,p,t[21][6][20],z;
int main()
{
fto(i,2,21)fto(j,0,6)fto(k,0,20)t[i][j][k]=-1<<25;fto(i,2,21)t[i][0][0]=0;
in>>n>>m;while(n--){in>>a;fto(p,2,21)
for(i=5;i;i--)for(j=0;j<p;j++)bmaxify(t[p][i][(j+a)%p],t[p][i-1][j]+a);}
while(m--){
    in>>k>>p;
    out<<max(t[p][k][0],-1)<<'\n';
}
}