#include <cstdio>
#define MAXN 300000
#define MAXK 5
#define MAXP 20
long long d[2][MAXK+1][MAXP+1][MAXP+1];
int v[MAXN+1];
inline long long getmax(long long a,long long b){
    if(a>b) return a;
    return b;
}
int main(){
    FILE*fi,*fout;
    int i,j,n,m,k,r,p,x;
    fi=fopen("tricouri.in" ,"r");
    fout=fopen("tricouri.out" ,"w");
    fscanf(fi,"%d%d" ,&n,&m);
    for(i=1;i<=n;i++)
        fscanf(fi,"%d" ,&v[i]);
    k=5;
    for(p=1;p<=20;p++)
     for(i=1;i<=n;i++)
       for(j=1;j<=k;j++)
         for(r=0;r<p;r++)
          if(d[1-i&1][j-1][r][p]%p==r)
           d[i&1][j][(r+v[i])%p][p]=getmax(d[1-i&1][j][(r+v[i])%p][p],getmax(d[1-i&1][j-1][r][p]+v[i],d[i&1][j][(r+v[i])%p][p]));
          else
           d[i&1][j][(r+v[i])%p][p]=getmax(d[1-i&1][j][(r+v[i])%p][p],d[i&1][j][(r+v[i])%p][p]);
    while(m>0){
        m--;
        fscanf(fi,"%d%d" ,&k,&p);
        if(d[n&1][k][0][p]==0)
              fprintf(fout,"-1\n");
        else
              fprintf(fout,"%lld\n" ,d[n&1][k][0][p]);
    }
    fclose(fi);
    fclose(fout);
    return 0;
}