Giải cứu cô W

Trong một buổi nghiên cứu về dinh dưỡng, FullHouse Dev bắt gặp một câu chuyện thú vị về việc tăng cường sức mạnh thông qua việc ăn uống và nghỉ ngơi hợp lý. Điều này gợi nhớ đến câu chuyện về anh S và hành trình giải cứu cô W khỏi quái vật Lười.

Bài toán

Cô W đã bị quái vật Lười bắt cóc. Là bạn trai của cô W, anh S phải giải cứu cô ấy. Để đánh bại quái vật Lười và cứu cô W khỏi việc biến thành sinh vật lười, anh S cần đạt được một cấp độ sức mạnh nhất định.

Hiện tại, anh S đang ở cấp độ \(X\) và cần đạt đến cấp độ \(Y\). Có nhiều phương pháp chuyển đổi khác nhau:

• Nếu chọn phương pháp thứ \(i\), anh có thể chuyển từ cấp độ \(Ai\) sang cấp độ \(Bi\) với chi phí thể lực là \(Zi\) (và ngược lại).
• Tại cấp độ \(i\), anh có thể ăn Trái Ác Quỷ đặc biệt, khiến anh ngủ \(Hi\) giờ và sau đó thể lực sẽ bằng \(Ci\).

Anh S có thể chọn ăn Trái Ác Quỷ hoặc không. Có thể có nhiều cách khác nhau để di chuyển giữa các cấp độ với chi phí thời gian ngủ khác nhau.

INPUT FORMAT:

• Dòng đầu tiên chứa 4 số nguyên \(N\) (số cấp độ), \(M\) (số phương pháp chuyển đổi), \(A\) (cấp độ ban đầu), \(B\) (cấp độ cần đạt).
• \(M\) dòng tiếp theo, mỗi dòng chứa 3 số nguyên \(X\), \(Y\), \(Z\), thể hiện có thể chuyển từ cấp độ \(X\) sang cấp độ \(Y\) với chi phí thể lực \(Z\).
• \(N\) dòng cuối, mỗi dòng chứa 2 số nguyên \(Ci\), \(Hi\), thể hiện tại cấp độ \(i\), có thể đạt thể lực \(Ci\) sau khi ngủ \(Hi\) giờ.

OUTPUT FORMAT:

• Một số nguyên duy nhất là thời gian ngủ tối thiểu cần thiết để đạt được cấp độ mục tiêu. Nếu không thể đạt được, in ra -1.

Ràng buộc:

• \(1 \leq N \leq 1000\)
• \(0 \leq M \leq 1000\)
• \(1 \leq \text{Cấp\_độ\_ban\_đầu}, \text{Cấp\_độ\_mục\_tiêu} \leq N\)
• \(1 \leq Xi, Yi \leq N\)
• \(1 \leq Zi \leq 10^9\)
• \(1 \leq Ci, Hi \leq 10^9\)

Ví dụ:

INPUT

3 3 1 3
1 2 2
1 3 3
3 2 1
2 7
2 7
3 6

OUTPUT

14

Giải thích:

• Đầu tiên, anh S ăn Trái Ác Quỷ ở cấp độ 1, ngủ 7 giờ và đạt thể lực 2.
• Sau đó chuyển sang cấp độ 2, tốn 2 thể lực.
• Tiếp tục ăn Trái Ác Quỷ ở cấp độ 2, ngủ 7 giờ và đạt thể lực 2.
• Cuối cùng chuyển sang cấp độ 3 với chi phí 1 thể lực.
• Tổng thời gian ngủ = 7 + 7 = 14 giờ.