#include<bits/stdc++.h> using namespace std; long long dp[100005],w[100005]; int n,q; int main(){ // freopen("div.in","r",stdin); // freopen("div.out","w",stdout); cin>>n>>q; for(int i = 1;i<=n;i++){ cin>>w[i]; } while(q--){ int x,y; cin>>x>>y; memset(dp,0x3f,sizeof dp); if(x<y){ cout<<0<<endl; continue; } for(int i = 0;i<=y;i++)dp[i]=0; for(int i = y;i<=x;i++){ for(int j = 1;j<=n;j++){ dp[i]=min(dp[i],dp[i/j]+w[j]); } } cout<<dp[x]<<endl; } }