提示: 欢迎访问OurACM平台。
Problem 2239 Daxia & Yayamao's problem

Accept: 22    Submit: 97
Time Limit: 2000 mSec    Memory Limit : 32768 KB

Problem Description

首先yayamao给定n对整数(a1,b1),(a2,b2),...,(ai,bi),...,(an,bn),并定义f(x)=max(ai*x+bi),

然后yayamao给出m个整数x1,x2,...,xi,...,xm,请daxia求出对应f(xi)的值,现请你帮daxia这个忙.

Input

测试包含多组数据.

每组数据第一行为2个整数n(0<n<=100000),m(0<m<=100000).

接下来包含n行,每行2个整数ai和bi(-1000000000<=ai,bi<=1000000000).

接下来包含m行,每行1个整数xi(-1000000000<=xi<=1000000000).

Output

每组数据输出m行整数,为对应f(x)的值.

Sample Input

3 3 0 -2 1 -2 2 -4 -1 1 3

Sample Output

-2 -1 2

Hint

f(-1)=max(-2,-3,-6)=-2

f(1)=max(-2,-1,-2)=-1

f(3)=max(-2,1,2)=2

Source

FOJ有奖月赛-2016年8月(daxia专场之过四题方有奖)

Submit  Back  Status  Discuss