Đường tới rạp chiếu phim

Vasya đang ở một dịch vụ cho thuê xe và muốn đến rạp chiếu phim. Bộ phim anh đã mua vé sẽ bắt đầu sau $t$ phút. Con đường từ dịch vụ đến rạp là một đường thẳng dài $s$ ki-lô-mét: dịch vụ ở toạ độ $0$, rạp ở toạ độ $s$.

Dọc đường có $k$ trạm xăng, tại mỗi trạm có thể đổ đầy nhiên liệu miễn phí và tức thời (không mất thời gian), nhưng không được đổ vượt quá dung tích bình xăng.

Có $n$ chiếc xe để thuê. Xe thứ $i$ có giá thuê $c_i$ và dung tích bình xăng $v_i$ lít. Ban đầu mọi xe đều được đổ đầy bình tại dịch vụ.

Mỗi xe có thể chạy ở một trong hai chế độ, và có thể đổi chế độ bất kỳ lúc nào, bao nhiêu lần tuỳ ý:

• Chế độ thường: đi $1$ km trong $2$ phút, tiêu tốn $1$ lít nhiên liệu.
• Chế độ tăng tốc: đi $1$ km trong $1$ phút, tiêu tốn $2$ lít nhiên liệu.

Hãy chọn chiếc xe có giá thuê nhỏ nhất sao cho Vasya có thể đến rạp không muộn hơn $t$ phút. Nếu không có xe nào phù hợp, in ra $-1$.

Dữ liệu vào

• Dòng đầu chứa bốn số nguyên dương $n$, $k$, $s$, $t$.
• $n$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên dương $c_i$ và $v_i$ — giá thuê và dung tích bình xăng của xe thứ $i$.
• Dòng cuối chứa $k$ số nguyên phân biệt $g_1,g_2,\dots ,g_k$ — vị trí các trạm xăng (theo thứ tự bất kỳ).

Dữ liệu ra

In ra giá thuê nhỏ nhất của một chiếc xe phù hợp, hoặc $-1$ nếu không có xe nào giúp Vasya đến rạp kịp giờ.

Ràng buộc

• $1\le n\le 2·{10}^5$
• $1\le k\le 2·{10}^5$
• $2\le s\le {10}^9$
• $1\le t\le 2·{10}^9$
• $1\le c_i,v_i\le {10}^9$
• $1\le g_i\le s-1$

Ví dụ