Sau Chapter II, khi nhận ra mình đã quay về năm 1962, Youtuber_TWK và doangiaphuc13 bắt đầu tìm hiểu xem họ đang ở đâu và chuyện gì đang xảy ra.

Chiếc máy thời gian đưa ra tọa độ mới.

LOCATION: CUBA

DATE: OCTOBER 1962

Youtuber_TWK nhìn màn hình.

"Cuba?"

Anh im lặng vài giây.

"Sao lại là Cuba?"

doangiaphuc13 bước tới chiếc radio cũ đặt bên cạnh.

Một bản tin đang được phát.

Những từ như CUBA, SOVIET UNION và MISSILES liên tục xuất hiện giữa tiếng radio rè rè.

doangiaphuc13 im lặng vài giây rồi nói:

"Anh biết chuyện gì đang xảy ra vào thời điểm này không?"

Youtuber_TWK:

"Khủng hoảng tên lửa Cuba..."

Cả hai nhìn nhau.

Họ đã rơi đúng vào tháng 10 năm 1962 — thời điểm căng thẳng giữa Hoa Kỳ và Liên Xô đang lên đến đỉnh điểm.

Nhưng Youtuber_TWK dường như chẳng có tâm trí để quan tâm quá nhiều đến tình hình bên ngoài.

Anh ngồi xuống chiếc ghế cũ bên cạnh cửa sổ.

Ánh mắt vẫn còn vẻ mệt mỏi kể từ trước khi hai người bước vào chiếc máy thời gian.

doangiaphuc13 nhìn anh.

"Anh vẫn còn nghĩ về chuyện đó à?"

Youtuber_TWK:

"Ừ."

"Biết là nên bỏ qua rồi."

"Nhưng đâu phải muốn quên là quên được."

doangiaphuc13 không nói gì.

Cậu kéo chiếc ghế bên cạnh lại rồi ngồi xuống.

"Thôi."

"Ít nhất giờ mình còn có việc phải làm."

Youtuber_TWK nhìn sang cậu.

"Ừ."

Anh quay lại nhìn ra ngoài cửa sổ.

Tiếng radio vẫn vang lên đều đều.

Những bản tin về tên lửa, quân đội và tình hình căng thẳng tại Cuba liên tục được phát.

Một lúc sau, Youtuber_TWK vô thức lấy điện thoại ra.

Màn hình hiện lên:

NO SIGNAL

Anh nhìn nó vài giây.

Rồi tắt màn hình.

doangiaphuc13:

"Anh vẫn còn giữ thói quen đó à?"

Youtuber_TWK:

"Ừ."

"Quen rồi."

Anh đặt điện thoại xuống bàn.

"Có chuyện gì trước đây cũng muốn kể cho người ta nghe."

"Giờ mở điện thoại lên mới nhớ ra là chẳng còn ai để kể nữa."

doangiaphuc13 nhìn anh một lúc.

"Thôi em nói rồi mà đời còn dài gái còn nhiều mà, đừng buồn nữa."

Youtuber_TWK khẽ gật đầu.

"Anh cũng muốn lắm chứ, nhưng lúc nào hình bóng cô ấy cũng luôn hiện trong tâm trí anh, làm anh không sao quên được."

Ngay lúc đó—

TEMPORAL CORE: LOW ENERGY

Âm thanh cảnh báo vang lên khắp căn phòng.

Youtuber_TWK lập tức đứng dậy.

"Không lẽ lại hết năng lượng?"

doangiaphuc13 mở bảng điều khiển.

"Không chỉ vậy."

Trên màn hình xuất hiện một bản đồ gồm \(n\) vị trí liên lạc.

Mỗi vị trí được đánh số từ \(1\) đến \(n\).

Giữa một số vị trí có các đường truyền tín hiệu.

Mỗi đường truyền có một mức năng lượng cần thiết để hoạt động.

Chiếc máy thời gian cần truyền một tín hiệu từ vị trí \(1\) đến vị trí \(n\) để khôi phục liên lạc với hệ thống điều khiển chính.

Nếu đi qua một đường truyền có chi phí \(w\), hệ thống sẽ tiêu tốn \(w\) đơn vị năng lượng.

Tuy nhiên, do tình trạng nhiễu sóng trong thời kỳ khủng hoảng, mỗi đường truyền chỉ có thể được sử dụng theo đúng chiều được ghi trên bản đồ.

Ngoài ra, hệ thống chỉ cho phép tín hiệu đi qua không quá \(k\) đường truyền.

Nếu tín hiệu đi qua các vị trí

thì tổng chi phí là

Một hành trình hợp lệ phải thỏa mãn

Một vị trí có thể xuất hiện nhiều lần trong hành trình. Tuy nhiên, hành trình không được sử dụng quá \(k\) đường truyền.

Chi phí không được vượt quá giới hạn năng lượng \(m\):

Youtuber_TWK nhìn bảng điều khiển.

"Vậy chỉ cần tìm đường rẻ nhất từ \(1\) đến \(n\)?"

doangiaphuc13:

"Đúng, nhưng phải tìm trong số những đường đi không vượt quá \(k\) bước."

Youtuber_TWK thở dài.

"Lại một bài nữa..."

Input

• Dòng đầu tiên chứa bốn số nguyên \(n,m,k,e\).
• \(n\) — số lượng vị trí liên lạc.
• \(m\) — lượng năng lượng tối đa mà máy thời gian có thể sử dụng.
• \(k\) — số đường truyền tối đa được phép đi qua.
• \(e\) — số lượng đường truyền.
• \(e\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(u,v,w\) mô tả một đường truyền có hướng từ \(u\) đến \(v\) với chi phí \(w\).

Output

• In ra chi phí nhỏ nhất của một hành trình từ vị trí \(1\) đến vị trí \(n\).
• Hành trình phải sử dụng không quá \(k\) đường truyền và có tổng chi phí không vượt quá \(m\).
• Nếu không tồn tại hành trình hợp lệ, in ra -1.

Example

6 20 4 7 1 2 4 1 3 2 2 4 5 3 4 4 4 5 3 5 6 2 2 3 1

11

5 10 2 5 1 2 3 1 3 4 2 4 4 3 4 2 4 5 3

-1

Ràng buộc

• \(2\le n\le1000\)
• \(1\le m\le10^9\)
• \(1\le k\le n-1\)
• \(1\le e\le5000\)
• \(1\le u,v\le n\)
• \(u\ne v\)
• \(1\le w\le10^6\)

Scoring

• Subtask (\(100\)%): Không có giới hạn bổ sung. Các test đều sử dụng đầy đủ giới hạn của đề bài.

Youtuber_TWK nhập xong dữ liệu.

Màn hình bắt đầu tính toán.

CALCULATING...

STEP 1/4

STEP 2/4

STEP 3/4

Bên ngoài cửa sổ, tình hình vẫn vô cùng căng thẳng.

Chiếc radio liên tục phát những bản tin mới.

doangiaphuc13 nhìn ra ngoài.

"Không khí ở đây đáng sợ thật."

Youtuber_TWK:

"Ừ."

Anh nhìn màn hình.

"Giải xong cái này rồi mình phải tìm cách rời khỏi đây."

STEP 4/4

Màn hình hiện:

ROUTE FOUND

ENERGY REQUIRED: 11

Youtuber_TWK nhìn kết quả.

"Xong."

Anh định nhấn nút xác nhận.

Nhưng ngay khi ngón tay vừa chạm vào bảng điều khiển—

BÍP!

Màn hình đột nhiên chuyển sang màu đỏ.

TEMPORAL DISTORTION DETECTED

Youtuber_TWK lập tức đứng dậy.

"Có gì đó không ổn."

Một tín hiệu lạ xuất hiện trên bản đồ.

UNKNOWN SIGNAL

ORIGIN: USSR

YEAR: 1983

Youtuber_TWK sững người.

"1983?"

doangiaphuc13 nhìn chằm chằm vào màn hình.

"Đó là năm được ghi trên chiếc hộp."

Cả hai im lặng.

Chiếc máy thời gian bắt đầu tự động ghi lại tín hiệu.

TEMPORAL SIGNAL SAVED

Youtuber_TWK:

"Tại sao tín hiệu từ năm 1983 lại xuất hiện ở đây?"

doangiaphuc13:

"Em không biết."

"Nhưng có vẻ nó đang cố kết nối với máy."

Một dòng chữ mới xuất hiện.

SIGNAL DESTINATION: 1963

Youtuber_TWK:

"1963?"

doangiaphuc13 nhìn lịch trên tường.

"Có vẻ tín hiệu này không phải được gửi đến chúng ta."

"Nó đang được gửi đến năm 1963."

Youtuber_TWK:

"Vậy tại sao máy lại nhận được?"

doangiaphuc13 chưa kịp trả lời thì—

TEMPORAL JUMP BLOCKED

Một tiếng còi vang lên.

BÍP! BÍP! BÍP!

Youtuber_TWK:

"Vậy chúng ta phải làm gì?"

doangiaphuc13 nhìn bản đồ.

Một điểm sáng mới xuất hiện ở phía bên kia Cuba.

"Tín hiệu có nguồn ở đó."

Youtuber_TWK:

"Nguồn tín hiệu?"

doangiaphuc13:

"Ừ."

"Nếu tìm được nơi phát tín hiệu, có thể chúng ta sẽ biết tại sao máy thời gian lại bị khóa."

Youtuber_TWK nhìn điểm sáng trên bản đồ.

Anh im lặng vài giây.

"Được."

"Đi thôi."

doangiaphuc13:

"Anh không nghỉ một chút à?"

Youtuber_TWK:

"Để sau."

Anh đứng dậy, cầm chiếc điện thoại đã mất tín hiệu từ lâu lên.

Nhìn màn hình NO SIGNAL thêm một lần, anh cất nó vào túi.

"Dù sao cũng chẳng có gì để xem."

Hai người rời khỏi căn phòng.

Bên ngoài, tiếng xe quân sự vang lên giữa màn đêm.

Ở phía xa, một đoàn xe đang di chuyển về hướng căn cứ.

Trên bảng điều khiển phía sau họ, tín hiệu bí ẩn vẫn tiếp tục nhấp nháy.

UNKNOWN SIGNAL

ORIGIN: USSR — 1983

DESTINATION: 1963

STATUS: ACTIVE

Không ai trong hai người biết tín hiệu này là gì.

Nhưng một điều chắc chắn—

Nó có liên quan đến chiếc máy thời gian.

Và có thể cả chiếc hộp mà họ đã tìm thấy trong kho đồ cũ của Liên Xô.

Youtuber_TWK nhìn về phía đoàn xe.

"Xem ra muốn về nhà cũng không dễ."

doangiaphuc13:

"Từ lúc chúng ta tìm thấy cái máy này đã có dễ lần nào đâu."

Youtuber_TWK:

"Cũng đúng."

Hai người tiếp tục bước vào màn đêm.

Phía sau họ, chiếc máy thời gian vẫn phát sáng.

Một dòng chữ cuối cùng xuất hiện trên màn hình:

NEXT TEMPORAL EVENT: 1986

Câu chuyện vẫn chưa kết thúc!!!!

Chuyến đi vượt thời gian: Chapter IV (Chemical Protocol)