#include<bits/stdc++.h> #define Max int(1e5) using namespace std; int dp[100005],w[100005]; int n,q; int main(){ // freopen("div.in","r",stdin); // freopen("div.out","w",stdout); memset(dp,0x3f,sizeof dp); cin>>n>>q; for(int i = 1;i<=n;i++){ cin>>w[i]; } dp[n]=w[n]; for(int i = n-1;i>=1;i--){ w[i]=min(w[i],w[i+1]);dp[i]=w[i]; } for(int i = 2;i<=Max;i++){ for(int j = 2;;j++){ long long z=min(Max,i*j); dp[z]=min(dp[z],dp[i]+dp[j]); if(z==1e5)break; } } for(int i = Max - 1 ; i >= 1 ; i --) dp[i] = min(dp[i] , dp[i + 1]) ; while(q--){ int x,y; scanf("%d%d",&x,&y); if(x<y){ cout<<0<<endl; continue; } int l = 0,r=x; while(l+1<r){ long long mid=(l+r)/2; if( x/mid<=y ) r=mid; else l=mid; } cout<<dp[r]<<endl; } }