#pragma GCC optimize(2) #include<bits/stdc++.h> const int Max= 100000; using namespace std; int dp[100005],w[100005]; int n,q; int main(){ std::ios::sync_with_stdio(false) , cin.tie(0) ,cout.tie(0); 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 = 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 ; } } for(int i = Max - 1 ; i >= 1 ;-- i ) { dp[i] = dp[i] > dp[i + 1] ? dp[i+1] : dp[i] ; } while(--q){ int x,y; cin>>x>>y; if(x<=y){ cout << "0\n"; continue; } int l = 1, r = x,ans=x; while (l < r) { int mid = l + r >> 1; if (x / mid <= y){r = mid;} else l = mid + 1; } cout << dp[l] << '\n'; } cout.flush(); return 0; }