#include <bits/stdc++.h>
const int NMAX = 3e5;
const int KMAX = 5;
const int PMAX = 20;
using namespace std;
ifstream fin ("tricouri.in");
ofstream fout ("tricouri.out");
int arr[NMAX + 5], n, q, k, p;
void solve_query(){
    int dp[KMAX + 5][PMAX + 5]; /// dp[i][j] - suma maxima formata din k tricouri cu restul j
    fin >> k >> p;
    for (int i = 0; i <= k; i++)
        for (int j = 0; j <= p; j++)
            dp[i][j] = -1;
    dp[0][0] = 0;
    for (int i = 1; i <= n; i++){
         for (int j = min(i, k); j >= 1; j--)
             for (int rest = p - 1; rest >= 0; rest--){
                  int chomp = (rest - arr[i] % p + p) % p;
                  if (dp[j - 1][chomp] != -1)
                     dp[j][rest] = max(dp[j][rest], dp[j - 1][chomp] + arr[i]);
             }
    }
    fout << dp[k][0] << "\n";
}
signed main(){
    fin >> n >> q;
    for (int i = 1; i <= n; i++)
         fin >> arr[i];
    while(q--)
        solve_query();
    return 0;
}