#include<bits/stdc++.h> using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n,q; cin>>n>>q; vector<int> b(n+1,0); for(int i=1;i<=n;i++) cin>>b[i]; vector<int> cost(100001,1000000000); 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<=1e5;i++){ for(int j=2;;j++){ int z=min(100000,j*i); cost[z]=min(cost[z],cost[i]+cost[j]); if(z==1e5) break; } } for(int i=1e5-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; } else l=mid+1; } cout<<cost[p]<<"\n"; } }