#include<bits/stdc++.h> #pragma GCC optimize(3) using namespace std; int dp[100005],w[100005]; const int Max= 100000; int n,q; int main(){ for(int i = 1;i<=Max;++i)dp[i]=0x3f3f3f3f; scanf("%d%d",&n,&q); for(int i = 1;i<=n;++i){ scanf("%d",&w[i]); } dp[n]=w[n]; for(register int i = n-1 ; i>=1 ; --i){ w[i]=min(w[i],w[i+1]); dp[i]=w[i]; } for(register int i = 2;i<=Max;++i){ for(register int j = 1;;++j){ int z=(Max>i*j) ? (i*j) : Max; dp[z]=((dp[z]<dp[i]+dp[j])?dp[z]:(dp[i]+dp[j])); if(z>=Max)break ; } }//i->1e5 j>1; // for(register int i = Max - 1 ; i >= 1 ;-- i ) { dp[i] = ((dp[i] > dp[i + 1]) ? dp[i+1] : dp[i] ); } register int x,y,l,r,ans,mid; while(--q){ scanf("%d%d",&x,&y); if(x<=y){ printf("0\n"); continue; } l = 1, r = x,ans=x; while (l <= r) { mid = (l + r) >> 1; if (x / mid <= y){r = mid - 1;ans=mid;} else l = mid + 1; } printf("%d\n",dp[ans]); } return 0; }