Tý cần giải bài toán sau:

An có \(N\) đường thẳng dạng \(y = a_i x + b_i\). An muốn biết với mỗi giá trị \(x\) cho trước, giá trị nhỏ nhất trong số các đường thẳng tại \(x\) là bao nhiêu.

Định dạng đầu vào

• Dòng đầu: hai số nguyên \(N, Q\) (\(1 \le N, Q \le 1000\)).
• \(N\) dòng tiếp: mỗi dòng \(a_i, b_i\) (\(-10^6 \le a_i, b_i \le 10^6\)).
• \(Q\) dòng tiếp: mỗi dòng chứa số nguyên \(x\) (\(-10^6 \le x \le 10^6\)).

Định dạng đầu ra

• Với mỗi truy vấn, in ra giá trị nhỏ nhất tìm được.

Ví dụ

Input:

4 3
1 0
-1 6
0 3
2 -4
0
2
5

Output:

0
1
6

Ràng buộc