#include <fstream>
using namespace std;

fstream f("tricouri.in",ios::in);
fstream g("tricouri.out",ios::out);

unsigned int a[6][22][300002],x[300002],n,m,r,k,p,i,j,k1,p1,sumnou,summax;

int main()
{
    f>>n>>m;
    for (i=1;i<=n;i++) f>>x[i];
    for (r=1;r<=m;r++)
    {
        f>>k>>p;
        for (i=1;i<=n;i++)
        {
            for (j=0;j<=i-1;j++)
            {
                for (k1=1;(k1<=i)&&(k1<=k);k1++)
                {
                    for (p1=0;p1<p;p1++)
                    {
                        sumnou=a[k1-1][p1][j]+x[i];
                        if (sumnou>a[k1][(sumnou)%p][i]) a[k1][sumnou%p][i]=sumnou;
                    }
                }
            }
            /*g<<i<<endl;
            g<<endl;
            for (k1=1;k1<=k;k1++)
            {
                for (p1=0;p1<p;p1++) g<<a[k1][p1][i]<<" ";
                g<<endl;
            }
            g<<endl;*/
        }
        summax=0;
        for (i=1;i<=n;i++)
        {
            if (a[k][0][i]>summax) summax=a[k][0][i];
        }
        for (i=1;i<=n;i++)
        {
            for (k1=1;k1<=k;k1++)
                for (p1=0;p1<p;p1++) a[k1][p1][i]=0;
        }
        if (summax==0) g<<"-1"<<endl;
                else g<<summax<<endl;
    }
    f.close();g.close();
    return 0;
}