#include<bits/stdc++.h> #define int long long using namespace std; int ans[100010]; int b[100010]; signed main(){ int n,q; cin>>n>>q; for(int i=1;i<=n;i++){ cin>>b[i]; } memset(ans,0x3f,sizeof(ans)); ans[1]=0; for(int i=1;i<=100000;i++){ for(int j=2;i*j<=100000&&j<=n;j++){ ans[i*j]=min(ans[i*j],ans[i]+b[j]); } } for(int i=100000-1;i>=1;i--){ ans[i]=min(ans[i],ans[i+1]); } for(int i=1;i<=q;i++){ int x,y; cin>>x>>y; cout<<ans[((x/y)+(x%y>0))/2+1]<<endl; } return 0; }