#include<bits/stdc++.h> using namespace std ; int main() { // freopen("div.in", "r", stdin); // freopen("div.out", "w", stdout); std::ios::sync_with_stdio(false) , cin.tie(0) ; int n , q ; cin >> n >> q ; vector<int> b(n + 1 , 0) ; for(int i = 1 ; i <= n ; i ++) cin >> b[i] ; const int up = 1e5 ; const int inf = 1e9 ; vector<int> cost(up + 1 , inf) ; for(int i = n - 1 ; i >= 1 ; i --) b[i] = min(b[i] , b[i + 1]) ; for(int i = 1 ; i <= n ; i ++) cost[i] = b[i] ; for(int i = 1 ; i <= up ; i ++) for(int j = 2 ; ; j ++) { int z = min(up , j * i) ; cost[z] = min(cost[z] , cost[i] + cost[j]) ; if(z == up) break ; } for(int i = up - 1 ; i >= 1 ; i --) cost[i] = min(cost[i] , cost[i + 1]) ; while(q --) { int x , y ; cin >> x >> y ; if(x <= y) { cout << "0\n" ; continue ; } int l = 1 , r = x ; int p = r ; while(l <= r) { int mid = (l + r) / 2 ; if(x / mid <= y) { p = mid ; r = mid - 1 ; } else l = mid + 1 ; } cout << cost[p] <<'\n' ; } cout<<endl; return 0 ; }