#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;

const int NMAX = 300010;

int N, V[NMAX], M, P, K, Max[6][21][21];

int main()
{
    freopen("tricouri.in", "r", stdin);
    freopen("tricouri.out", "w", stdout);

    scanf("%i %i", &N, &M);
    for(int i = 1; i <= N; ++ i)
        scanf("%i", &V[i]);

    for(int i = 0; i < 6; ++ i)
        for(int j = 0; j < 21; ++ j)
            for(int k = 0; k < 21; ++ k)
                Max[i][j][k] = -1;

    for(int i = 2; i <= 20; ++ i)
        Max[0][i][0] = 0;

    for(int i = 1; i <= N; ++ i)
        for(int j = 4; j >= 0; -- j)
            for(int k = 2; k <= 20; ++ k)
                for(int l = 0; l < k; ++ l)
                    if(Max[j][k][l] != -1)
                        Max[j + 1][k][(Max[j][k][l] + V[i]) % k] = max(Max[j + 1][k][(Max[j][k][l] + V[i]) % k], Max[j][k][l] + V[i]);

    for(; M; M --)
    {
        scanf("%i %i", &K, &P);
        printf("%i\n", Max[K][P][0]);
    }

    return 0;
}