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

Điểm: 1,00 (OI)

Giới hạn thời gian: 0.3s

Python 3 1.5s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

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 \leq N \leq 50 000$
$1 \leq G \leq 10^{6}$
$0 \leq B \leq D$
$1 \leq D \leq 10^{9}$
$0 \leq X_{i} \leq D$
$1 \leq Y_{i} \leq 10^{6}$

Ví dụ

Input	Output	Giải thích
4 10 3 17 2 40 9 15 5 7 10 12	174	Mua xăng rẻ tại trạm vị trí 5 (giá 7) và trạm vị trí 9 (giá 15) để đến đích với tổng chi phí 174.
10 10 10 1000 731 467592 386 754369 215 837197 851 407143 9 401476 943 234795 779 839893 269 385425 199 58693 745 725521	-1	Không thể đến đích vì khoảng cách giữa các trạm vượt quá sức chứa bình xăng.

Bình luận

Không có bình luận tại thời điểm này.