#include<bits/stdc++.h> using namespace std; #define int long long const int N=1e5,mmax=1e14; int n,q,x,y; int b[N+10],cost[N+10]; signed main(){ // freopen("div.in","r",stdin); // freopen("div.out","w",stdout); cin>>n>>q; for(int i=1;i<=n;i++)cin>>b[i]; memset(cost,0x3f,sizeof(cost)); for(int i=n;i>=1;i--){ // cout<<cost[i+1]<<" "<<b[i]<<endl; cost[i]=min(cost[i+1],b[i]); } // for(int i=1;i<=N+1;i++)cout<<cost[i]<<" "; // cout<<endl; for(int i=1;i<=N;i++){ for(int j=1;;j++){ int p=min(N,i*j); cost[p]=min(cost[p],cost[i]+cost[j]); if(p==N)break; } } for(int i=N-1;i>=1;i--)cost[i]=min(cost[i],cost[i+1]); // for(int i=1;i<=n;i++)cout<<cost[i]<<" "; // cout<<endl; while(q--){ cin>>x>>y; if(x<=y){cout<<0<<endl;continue;} int l=1,r=x; while(l<r){ int mid=(l+r)>>1; if((x/mid)<=y)r=mid; else l=mid+1; } cout<<cost[l]<<endl; } return 0; }