#import <fstream>
std::fstream f("tricouri.in"), g("tricouri.out", std::_S_out);
int n, k, p, i, j, s, A[32][32][8];
void h(int k, int x, int i, int j = 0)
{
  if (i - p)
    for (h(k, x, i + 1); n = A[p][i][j], j < k && n; h(k - j++ - 1, x += n, i + 1))
      ;
    s = k || s >= x || x % p ? s : x;
}
main()
{
  for (f >> n >> s; n--;)
    for (f >> j, i = 2; p = j % i, i < 21; A[i++][p][k] = j)
      for (k = 5; k && j > (s = A[i][p][k - 1]); A[i][p][k--] = s)
        ;
  for (; f >> k >> p; g << s << '\n')
    s = -1, h(k, 0, 0);
}