Tiết Kiệm Nhiên Liệu

Bạn cần di chuyển quãng đường $D$ đơn vị bằng một chiếc xe tải. Xe có thể chứa tối đa $G$ đơn vị nhiên liệu và tiêu thụ đúng 1 đơn vị nhiên liệu cho mỗi đơn vị đường đi. Bạn bắt đầu với $B$ đơn vị nhiên liệu.

Trên đường có $N$ trạm xăng. Mỗi trạm có vị trí $X_i$ và giá nhiên liệu $Y_i$ (mỗi đơn vị). Bạn có thể mua bất kỳ lượng nhiên liệu nào (không vượt quá sức chứa bình) tại mỗi trạm.

Hãy tính chi phí mua nhiên liệu tối thiểu để đi từ vị trí 0 đến vị trí $D$, hoặc $-1$ nếu không thể thực hiện được.

Dữ liệu vào

• Dòng 1: Bốn số nguyên $N$, $G$, $B$, $D$.
• $N$ dòng tiếp theo: Mỗi dòng gồm hai số nguyên $X_i$ và $Y_i$ (vị trí và giá nhiên liệu của trạm thứ $i$).

Dữ liệu ra

Một số nguyên duy nhất: chi phí tối thiểu, hoặc $-1$ nếu không thể đến đích.

Ràng buộc

• $1\le N\le 50000$
• $1\le G\le {10}^6$
• $0\le B\le D$
• $1\le D\le {10}^9$
• $0\le X_i\le D$
• $1\le Y_i\le {10}^6$

Ví dụ