#include <cstdio>
#define MAXN 300000
#define MAXK 5
#define MAXP 20
using namespace std;
int d[2][MAXK+1][MAXP+1][MAXP], v[MAXN+1], n, m;
char rest[2][MAXK+1][MAXP+1][MAXP];
inline int maxim(int a, int b)
{
    if(a>b)
        return a;
    return b;
}
int main()
{
    freopen("tricouri.in", "r", stdin);
    freopen("tricouri.out", "w", stdout);
    int i, j, t, r, k, p;
    scanf("%d%d", &n, &m);
    for(i=1;i<=n;i++)
        scanf("%d", &v[i]);
    for(t=2;t<=MAXP;t++)
        rest[0][0][t][0]=1;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=MAXK;j++)
            for(t=2;t<=MAXP;t++)
                for(r=0;r<MAXP;r++)
                    d[i%2][j][t][r]=d[(i+1)%2][j][t][r];
        for(j=1;j<=MAXK;j++)
            for(t=2;t<=MAXP;t++)
                for(r=0;r<t;r++)
                    if(rest[(i+1)%2][j-1][t][r]){
                        d[i%2][j][t][(r+v[i])%t]=maxim(d[i%2][j][t][(r+v[i])%t], d[(i+1)%2][j-1][t][r]+v[i]);
                        rest[i%2][j][t][(r+v[i])%t]=1;
                    }
    }
    for(i=1;i<=m;i++)
    {
        scanf("%d%d", &k, &p);
        if(d[n%2][k][p][0]==0)
            printf("-1\n");
        else printf("%d\n", d[n%2][k][p][0]);
    }
    return 0;
}