#include <cstdio> #include <iostream> #include <algorithm> #include <cstring> using namespace std; int n, q, b[100010]; long long f[100010]; long long dfs(int x, int y) { if (x <= y) return f[x] = 0; if (f[x] != 9e18) return f[x]; for (int i = 2; i <= n; i++) f[x] = min(f[x], dfs(x / i, y) + b[i]); return f[x]; } int main() { scanf("%d %d", &n, &q); for (int i = 1; i <= n; i++) scanf("%d", &b[i]); while (q--) { int x, y; scanf("%d %d", &x, &y); for (int i = 0; i <= x; i++) f[i] = 9e18; printf("%lld\n", dfs(x, y)); } return 0; }