Find the maximum of ax+b You are given a list of (a,b), and a list of x. Compute the maximum ax+b for each x. You can assume a, b and x are non-negative integers.

Your program or function must run in expected (to the randomness if your code involves that, not the input) O(nlogn) time where n is the total input length (sum or maximum of the lengths of both lists).

This is code-golf. Shortest code wins.

Example

[[2 8] [4 0] [2 1] [1 10] [3 3] [0 4]] [1 2 3 4 5]


Output:

[11 12 14 16 20]


Explanation:

11 = 1*1 + 10
12 = 1*2 + 10 = 2*2 + 8
14 = 2*3 + 8
16 = 2*4 + 8 = 4*4 + 0
20 = 4*5 + 0


Note about the complexity:

If you used a builtin having a good average-case complexity, and it can be randomized to get the expected complexity easily in theory, you can assume your language did that.

That means, if your program can be tested to be in O(nlogn), possibly with edge case exceptions because of the implementation of your language, but cannot be seen logically in your own code, we'll say it is O(nlogn).
Python, 214 bytes

S=sorted
def M(L,X):
 H=[-1,0];R={}
 for a,b in S(L):
    while H[2:]and a*H[-3]+b&gt;H[-2]*H[-3]+H[-1]:H=H[:-3]
    H+=[1.*(H[-1]-b)/(a-H[-2]),a,b]
 for x in S(X):
    while H[2:]and x&gt;H[2]:H=H[3:]
    R[x]=H[0]*x+H[1]
 return R


Computes the convex hull by iterating through the input a,b in increasing a order.  The convex hull is recorded in H using the format -1,0,x1,a1,b1,x2,a2,b2,x2,...,xn,an,bn where xi is the x coordinate of the intersection of a{i-1},b{i-1} and ai,bi.

Then I iterate though the input xs in sorted order, truncating the convex hull to keep up as I go.

Everything is linear except for the sorts which are O(n lgn).

Run it like:

&gt;&gt;&gt; print M([[2,8],[4,0],[2,1],[1,10],[3,3],[0,4]], [1,2,3,4,5])
{1: 11, 2: 12, 3: 14, 4: 16, 5: 20}