Attempt

Please login to see your submissions result.

Problem

Trong thời đại thần thoại Ánh Sương, vương quốc Eldoria muốn rước Thánh Hỏa từ Đền Bình Minh về Kinh Đô để làm lễ đăng quang. Nhiệm vụ được giao cho đoàn kỵ sĩ hộ tống do tướng trẻ Arion dẫn đầu. Arion phải chọn một trong số nhiều thần thú đang ràng buộc ở Chuồng Thiêng: mỗi thần thú có giá chuộc khác nhau và một bầu linh lực có thể tích trữ tối đa một lượng năng lượng nhất định.

Con đường từ Kinh Đô đến Đền Bình Minh là một tuyến thẳng dài ~d~ dặm. Trên đường có đặt q miếu tế (điểm an trú), tại mỗi miếu bầu linh lực sẽ được nạp đầy ngay khi đoàn tới nơi. Mỗi thần thú có thể di chuyển với hai nhịp:

• Nhịp thường: tốc độ 1 dặm/đơn vị thời gian, tiêu hao 1 đơn vị linh lực cho mỗi dặm đã đi.
• Nhịp thần tốc: tốc độ 2 dặm/đơn vị thời gian, tiêu hao 2 đơn vị linh lực cho mỗi dặm đã đi.

Trong từng quãng đường giữa hai điểm dừng liên tiếp (Kinh Đô → miếu 1, miếu 1 → miếu 2, …, miếu q → Đền), Arion có thể tùy ý thay đổi nhịp di chuyển, miễn là tổng linh lực tiêu thụ trên quãng ấy không vượt quá sức chứa của bầu linh lực của thần thú đã chọn. Nghi lễ bắt đầu sau đúng ~t~ đơn vị thời gian kể từ lúc rời Kinh Đô; nếu đến muộn, Thánh Hỏa sẽ tắt.

Hãy giúp Arion chọn một thần thú sao cho:

1) Có thể đi trọn hành trình mà không cạn linh lực giữa đường (nhờ nạp đầy tại các miếu),
2) Thời gian ngắn nhất có thể đạt được với thần thú đó không vượt quá ~t~,
3) Giá chuộc là nhỏ nhất trong số các thần thú thỏa hai điều kiện trên.

Nếu có thần thú phù hợp, hãy in giá chuộc nhỏ nhất; nếu không, in No hope!.

Input

• Dòng 1: bốn số nguyên ~n, q, d, t~ — số thần thú, số miếu tế, chiều dài đường và hạn thời gian.
• ~n~ dòng tiếp theo: dòng thứ ~i~ chứa hai số nguyên ~v[i], f[i]~ — giá chuộc và sức chứa linh lực của thần thú thứ ~i~.
• ~q~ dòng tiếp theo: mỗi dòng chứa số nguyên ~a[j]~ — vị trí miếu thứ ~j~ tính từ Kinh Đô (đơn vị dặm).

Output

In ra giá chuộc nhỏ nhất của một thần thú thỏa yêu cầu. Nếu không có, in No hope!.

Constraints

• ~1 \le n, q \le 10^5~
• ~1 \le d \le 2 \cdot 10^9~
• ~1 \le t \le 10^{9}~
• ~1 \le v[i], f[i] \le 10^{9}~
• ~1 \le a[j] \le d-1~ và các ~a[j]~ đôi một khác nhau.

Sample