#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("20241004T3.out","w",stdout); scanf("%lld%lld",&n,&q); for(int i=1;i<=n;i++)scanf("%lld",&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=2;;j++){ int p=min(N,i*j); cost[p]=min(cost[p],cost[i]+cost[j]); if(i*j>=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--){ scanf("%lld%lld",&x,&y); if(x<=y){printf("0\n");} else{ int l=1,r=x; while(l<r){ int mid=(l+r)>>1; if((x/mid)<=y)r=mid; else l=mid+1; } printf("%lld\n",cost[l]); } } return 0; }