#include<bits/stdc++.h> #define Max 100000LL #define gsy return #define will 0 #define AC ; using namespace std; int dp[100005],w[100005]; int n,q; int main(){ ios::sync_with_stdio(0); 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++){ long long z=min(Max,1ll*i*j); dp[z]=min(dp[z],dp[i]+dp[j]); if(z==Max)break ; } } for(int i = Max - 1 ; i >= 1 ; i --) { dp[i] = min(dp[i] , dp[i + 1]) ; } while(q--){ int x,y; cin>>x>>y; if(x<=y){ cout<<0<<endl; continue; } int l = 1, r = 1e9; while (l+1 < r) { int mid = l + r >> 1; if (mid < y / x)l = mid ; else r = mid; } cout<<dp[r]<<endl; } gsy will AC }