Tý có một công ty viễn thông đang thử nghiệm các gói cước mới. Có \(N\) gói cước, mỗi gói có dạng: cước phí hàng tháng là \(a \times X + b\), trong đó \(X\) là số phút sử dụng thực tế.

Có \(M\) khách hàng khác nhau, mỗi khách hàng có nhu cầu sử dụng \(x_j\) phút mỗi tháng. Công ty muốn với mỗi khách hàng, hãy tìm gói cước rẻ nhất (chi phí thấp nhất) cho họ.

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

• Dòng đầu chứa hai số nguyên \(N\) (\(1 \le N \le 10^5\)) và \(M\) (\(1 \le M \le 10^5\)).
• \(N\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(a_i, b_i\) (\(-10^9 \le a_i, b_i \le 10^9\)).
• Dòng cuối chứa \(M\) số nguyên \(x_1, x_2, \dots, x_M\) (\(-10^9 \le x_j \le 10^9\)).

Định dạng đầu ra

• In ra \(M\) số nguyên, mỗi số là chi phí rẻ nhất (giá trị \(a_i \times x_j + b_i\) nhỏ nhất) cho khách hàng thứ \(j\).

Ví dụ

Input:

3 4
2 5
-1 3
0 10
-5 0 7 3

Output:

-5 3 19 2

Giải thích: Với \(x=-5\): \(2\times(-5)+5=-5\); \(-1\times(-5)+3=8\); \(0\times(-5)+10=10\) → chọn \(-5\).

Ràng buộc

• Subtask 1 (30%): \(N, M \le 2000\).
• Subtask 2 (30%): \(N, M \le 10^4\).
• Subtask 3 (40%): \(N, M \le 10^5\).