有一堆向量\(A_i\)，多次询问向量\(P\)，查\(\max_{L\le R}P\times \sum_{i=L}^R A_i\)。

\(n\le 10^5\)

---

设向量\(P=(A,B)\)，区间和为\((X,Y)\)。需要最大化\(F=AY-BX\)。于是\(Y=\frac{B}{A}X+\frac{F}{A}\)。以\(A>0\)为例，相当于在\((X,Y)\)引一条斜率\(\frac{B}{A}\)的直线，求所有这样的\((X,Y)\)引出的直线的最大截距。

于是答案一定在所有\((X,Y)\)组成的凸包上。如果能求出这个凸包，就可以直接在上凸壳上二分在\(O(\lg)\)的时间内得到答案。

以下是构建这个凸包的方式：分治构造，求出\([L,mid],[mid+1,R]\)内的凸包，以及跨过中点的。对于跨过中点的，对左区间做后缀和，对右区间做前缀和，两者闵科夫斯基和。然后把得到的这三个凸包合并起来。

因为一个分治区间最多贡献区间长度的点数，总点数不超过区间总长，即\(O(n\lg n)\)。因为中间还需要归并，时间至少\(O(n\lg^2n)\)。

（诶所以我的实现方式是\(O(n\lg^3 n)\)？）

---

第一次写凸包（平常只是维护个凸壳）+第一次写闵科夫斯基和。

其实凸包可以直接分别维护上凸壳和下凸壳，应该更好写，也方便优化（在已经排好序的情况下，凸包合并应该可以线性做）

这次用极角排序的方式写凸包，有点细节。

求凸包和闵科夫斯基和的时候都需要找到最左端（坐标相同就最下端）的点作为基准点，从它开始跑，因为这样保证了这个点一定在凸包上。

然后凸包合并的时候我重新求了一次凸包，所以时间多了一个\(O(\lg)\)。

using namespace std;
#include <bits/stdc++.h>
#define N 100005
#define ll long long
#define db long double
int n,Q;
struct DOT{
	ll x,y;
	DOT(ll _x=0,ll _y=0){x=_x,y=_y;}
	db len2(){return (db)x*x+(db)y*y;}
} d[N];
bool operator<(DOT a,DOT b){return a.x<b.x || a.x==b.x && a.y<b.y;}
DOT operator+(DOT a,DOT b){return (DOT){a.x+b.x,a.y+b.y};}
DOT operator-(DOT a,DOT b){return (DOT){a.x-b.x,a.y-b.y};}
db cro(DOT a,DOT b){return (db)a.x*b.y-(db)a.y*b.x;}
vector<DOT> q[N*4],u,v;
vector<DOT> qa;
bool cmparc(DOT a,DOT b){return cro(a,b)>0 || cro(a,b)==0 && a.len2()<b.len2();}
void getcon(vector<DOT> &w){
	DOT O=w[0];
	for (int i=1;i<w.size();++i)
		O=min(O,w[i]);
	qa.clear();
	for (int i=0;i<w.size();++i)
		if (w[i].x!=O.x || w[i].y!=O.y)
			qa.push_back(w[i]-O);
	sort(qa.begin(),qa.end(),cmparc);
	static DOT st[N*20];
	int tp;
	st[tp=1]=DOT(0,0);
	for (int i=0;i<qa.size();++i){
		while (tp>1 && cro(st[tp]-st[tp-1],qa[i]-st[tp-1])<=0)
			--tp;
		st[++tp]=qa[i];
	}
	while (tp>1 && cro(st[tp]-st[tp-1],DOT(0,0)-st[tp-1])<0)
		--tp;
	w.clear();
	for (int i=1;i<=tp;++i)
		w.push_back(st[i]+O);
}
void getsum(vector<DOT> &w){
	DOT O=u[0]+v[0];
	u.push_back(u[0]);
	v.push_back(v[0]);
	w.clear();
	w.push_back(O);
	int i=0,j=0;
	while (i<u.size()-1 || j<v.size()-1)
		if (i<u.size()-1 && (j==v.size()-1 || cro(u[i+1]-u[i],v[j+1]-v[j])>0))
			w.push_back(O=O+u[i+1]-u[i]),i++;
		else
			w.push_back(O=O+v[j+1]-v[j]),j++;
	w.pop_back();
}
void merge(vector<DOT> &a,vector<DOT> &b){
	for (int i=0;i<b.size();++i)
		a.push_back(b[i]);
	b.clear();
}
void divide(int k,int l,int r){
	if (l==r){
		q[k].push_back(d[l]);
		return;
	}
	int mid=l+r>>1;
	divide(k<<1,l,mid);
	divide(k<<1|1,mid+1,r);
	u.clear(),v.clear();
	DOT s(0,0);
	for (int i=mid;i>=l;--i)
		s=s+d[i],u.push_back(s);
	s=DOT(0,0);
	for (int i=mid+1;i<=r;++i)
		s=s+d[i],v.push_back(s);
	getcon(u);
	getcon(v);
	getsum(q[k]);
	merge(q[k],q[k<<1]);
	merge(q[k],q[k<<1|1]);
	getcon(q[k]);
}
vector<DOT> f,g;
ll ask(vector<DOT> &h,DOT p){
	ll ans=0;
	for (int i=0;i<h.size();++i){
		ans=max(ans,(ll)cro(p,h[i]));
	}
	return ans;
	int l=0,r=(int)h.size()-2,res=h.size()-1;
	while (l<=r){
		int mid=l+r>>1;
		if (cro(p,h[mid+1]-h[mid])<=0)
			r=(res=mid)-1;
		else
			l=mid+1;
	}
	return cro(p,h[res]);
}
int main(){
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
//	freopen("area.in","r",stdin);
//	freopen("area.out","w",stdout);
	scanf("%d%d",&n,&Q);
	for (int i=1;i<=n;++i)
		scanf("%lld%lld",&d[i].x,&d[i].y);
	divide(1,1,n);
	DOT lef=q[1][0],rig=q[1][0];
	int pos=0;
	for (int i=1;i<q[1].size();++i)
		if (rig<q[1][i])
			rig=q[1][i],pos=i;
	for (int i=0;i<=pos;++i) f.push_back(DOT(q[1][i].x,-q[1][i].y));
	g.push_back(lef);
	for (int i=q[1].size()-1;i>=pos;--i) g.push_back(q[1][i]);
	while (Q--){
		ll A,B;
		scanf("%lld%lld",&A,&B);
		ll ans=0;
		if (A==0){
			if (B==0)
				ans=0;
			else
				ans=max(-B*lef.x,-B*rig.x);
		}
		else if (A>0)
			ans=ask(g,DOT(A,B));
		else
			ans=ask(f,DOT(-A,B));
		printf("%lld\n",ans);
	}
	return 0;
}