#include <bits/stdc++.h>

using namespace std;

ifstream fin("tricouri.in");
ofstream fout("tricouri.out");

int n,dp[7][25],i,t,x,j,i2,j2,val,a,b;

int main()
{
fin>>n>>t;
for(i=1;i<=n;i++){
    fin>>x;
    for(i2=1;i2<=5;i2++){
        for(j=1;j<=20;j++){
            if(dp[i2][j]){
                val = x + dp[i2][j];
                for(j2=1;j2<=20;j2++){
                    if(val % j2 == 0){
                        dp[i2+1][j2] = max(dp[i2+1][j2],dp[i2][j]+x);
                    }
                }
            }
        }
    }
    for(j=1;j<=20;j++){
        if(x % j == 0){
            dp[1][j] = max(dp[1][j],x);
        }
    }
}
while(t--){
    fin>>a>>b;
    if(!dp[a][b])
       fout << -1 << '\n';
    else
        fout << dp[a][b] << '\n';
}
    return 0;
}