Khu rừng nguyên sinh X nằm trên một đường thẳng dài mà ta có thể coi như trục tọa độ. Chỉ có thể đi chuyển vào cánh rừng bằng cách sử dụng trực thăng để bay tới một trong các điểm tập kết đã được xây dựng sẵn trong khu rừng. Điểm tập kết thứ ~i~ nằm ở tọa độ ~a_i~, chuyến bay tới đó tốn ~b_i~ đơn vị nhiên liệu. Mỗi đội thám hiểm sau khi hạ cánh ở một điểm tập kết sẽ tiếp tục sử dụng phương tiện đường bộ để di chuyển đến điểm thám hiểm. Chi phí di chuyển bằng phương tiện đường bộ là ~c~ đơn vị nhiên liệu cho mỗi đơn vị khoảng cách.

Có ~m~ đội thám hiểm, đội thứ ~j~ (~1 \le j \le m~) muốn đến thám hiểm ở vị trí có tọa độ ~d_j~, họ có thể chọn bay tới một điểm tập kết tùy ý, sau đó di chuyển tiến hoặc lùi trên bộ để đến đích.

Với mỗi đội thám hiểm, hãy tính xem họ cần tốn ít nhất bao nhiêu đơn vị nhiên liệu để tới được điểm thám hiểm của mình.

Dữ liệu

• Dòng 1: chứa ba số nguyên ~n, m, c~ (~1 \le n, m \le 10^5~, ~1 \le c \le 10^9~);
• Tiếp theo là ~n~ dòng, mỗi dòng mô tả một điểm tập kết gồm hai số nguyên ~a_i, b_i~ (~0 \le a_i, b_i \le 10^9~), không có hai điểm tập kết nào cùng tọa độ;
• Cuối cùng là ~m~ dòng, mỗi dòng gồm một số nguyên ~d_j~ (~1 \le d_j \le 10^9~), mô tả tọa độ cần đến của các đội thám hiểm.

Kết quả

Ghi trên ~m~ dòng, dòng thứ ~j~ ghi tổng chi phí nhỏ nhất để đội thám hiểm thứ ~j~ đến được tọa độ ~d_j~.

Ví dụ

expfuel.inp

3 2 1
200 300
300 100
100 250
150
110

expfuel.out

250
260

Giải thích:

• Đội 1: bay đến điểm tập kết tọa độ 300, tiêu tốn 100 đơn vị nhiên liệu, sau đó đi đến tọa độ 150, tốn thêm 150 đơn vị nhiên liệu.
• Đội 2: bay đến điểm tập kết tọa độ 100, tiêu tốn 250 đơn vị nhiên liệu, sau đó đi đến tọa độ 110, tốn thêm 10 đơn vị nhiên liệu.

Giới hạn

• Subtask 1 (40% số điểm): ~1 \le n, m \le 20~.
• Subtask 2 (20% số điểm): ~20 < n, m \le 1000~.
• Subtask 3 (40% số điểm): không có ràng buộc bổ sung.