#include<bits/stdc++.h> using namespace std; #define int long long const int N=1e5,INF=1e9; int n,q,b[N+10]; vector<int> cost(N+1,INF); int x,y; void init(){ for(int i=n-1;i>=1;i--){ b[i]=min(b[i],b[i+1]); } for(int i=1;i<=n;i++) cost[i]=b[i]; for(int i=1;i<=N;i++){ for(int j=2;;j++){ int z=min(N,i*j); cost[z]=min(cost[z],cost[i]+cost[j]); if(z>=N) break; } } for(int i=N-1;i>=1;i--) cost[i]=min(cost[i],cost[i+1]); return ; } int erfen(){ int l=1,r=x; int mid,p=x; while(l<r){ mid=(l+r)>>1; if((x/mid)<=y){ r=mid; }else l=mid+1; } return l; } signed main(){ scanf("%lld%lld",&n,&q); for(int i=1;i<=n;i++) scanf("%lld",&b[i]); init(); while(q--){ scanf("%lld%lld",&x,&y); if(x<=y) printf("0\n"); else printf("%lld\n",cost[erfen()]); } return 0; }