#include<cstdio>
#define NMAX 300000+5
#define MMAX 100+5
#define KMAX 5+2
#define PMAX 20+2
using namespace std;
int N,M,P,K,V[NMAX],m[NMAX][KMAX][PMAX];
int solve()
{
    int i,j,k,s;
    for(j=1;j<=K;j++)
    {
        //printf("j = %d\n",j);
        for(k=0;k<=P-1;k++)
        {
            //for(i=1;i<=j-1;i++) printf("0 ");
            for(i=j;i<=N;i++)
            {
                s=(m[i-1][j-1][(P+k-V[i]%P)%P]+V[i]);
                if(s%P==k && s>m[i-1][j][k]) m[i][j][k]=s;
                else m[i][j][k]=m[i-1][j][k];
                //printf("%d ",m[i][j][k]);
            }
            //printf("\n");
        }
    }
    if(m[N][K][0]==0) return -1;
    return m[N][K][0];
}
int main()
{
    int i;
    freopen("tricouri.in","r",stdin);
    freopen("tricouri.out","w",stdout);
    scanf("%d%d",&N,&M);
    for(i=1;i<=N;i++) scanf("%d",&V[i]);
    for(;M;--M)
    {
        scanf("%d%d",&K,&P);
        printf("%d\n",solve());
    }
    return 0;
}