#include<bits/stdc++.h> using namespace std; long long n,q,b[100005],nmin; long long dp[100005]; long long y,xx; long long dfs(long long x){ if(dp[x]!=0x3f3f3f3f3f3f3f3f){ return dp[x]; } if(x>=xx)return 0; for(int i=2;i<=n;i++){ for(int j=x*i;j<=xx*2;j++){ if(j/i!=x)break; dp[x]=min(dp[x],dfs(j)+b[i]); } } if(x<=y){ nmin=min(nmin,dp[x]); } return dp[x]; } int main(){ //freopen("div.in","r",stdin); //freopen("div.out","w",stdout); scanf("%lld%lld",&n,&q); for(int i=1;i<=n;i++){ scanf("%lld",&b[i]); } while(q--){ scanf("%lld%lld",&xx,&y); for(int i=0;i<=xx;i++){ dp[i]=0x3f3f3f3f3f3f3f3f; } nmin=0x3f3f3f3f3f3f3f3f; if(y>=xx){ printf("0\n"); continue; } long long t=dfs(1); printf("%lld\n",min(nmin,t)); } }