#include <iostream>
#include <fstream>

using namespace std;

ifstream f("tricouri.in");
ofstream g("tricouri.out");

#define nmax 300005

int n, m, a[nmax], dp[nmax][6][21];

void citeste(){

   f >> n >> m;
   for(int i=1; i<=n; i++) f >> a[i];

}

void rezolva(){

   //am m query in care am k si p si trebuie sa aleg k elemente din sir a.i. sa aiba suma maxima si suma aceasta sa fie divizibila cu P
   //preprocesez toate posibilitatile;
   //adica : dp[i][k][p] = suma maxima avand k elemente din primele i si suma asta sa fie divizibila cu P; si are restul la P = 0; dp[i][k][p] % P = 0;
   //folosind elementul a[i]

   int rez = 0;

   for(int i=1; i<=n; i++){
      for(int k=1; k<=5; k++){
         for(int p=2; p<=20; p++){
            int Max = 0;
            for(int j=i-1; j>=1; j--){
               for(int p2=2; p2<=20; p2++){
                  if (dp[j][k-1][p2] % p + a[i] % p == p){
                     Max = max(Max,dp[j][k-1][p2]);
                  }
               }
            }
            if (Max > 0 )dp[i][k][p] = Max + a[i];
            if (Max == 0 && k==1 && a[i] % p == 0) dp[i][k][p] = a[i];
         }
      }
   }

   for(int i=1; i<=m; i++){
      int x,y;
      f >> x >> y;
      int Max = 0;
      for(int j=1; j<=n; j++) Max = max(Max, dp[j][x][y]);
      if (Max == 0){
         g << "-1" << "\n";
      }else g << Max << "\n";
   }

}

int main(){

   citeste();
   rezolva();

   f.close();
   g.close();

   return 0;

}