Để vận chuyển hòm báu vật lên phòng làm việc của mình ở tầng N trong toà nhà chọc trời, Cuội phải thuê công nhân bốc vác để vận chuyển hòm. Biết các chi phí liên quan đến thuê công nhân là: để di chuyển theo thang bộ lên trên một tầng là
U, xuống dưới một tầng là D, khênh hòm vào thang máy là I,
khênh hòm ra khỏi thang máy là J.
Trong toà nhà có L thang máy, mỗi thang chỉ dừng ở những tầng nhất định. Việc di chuyển theo thang máy là miễn phí.
Yêu cầu: Hãy giúp Bờm tìm đường vận chuyển hòm báu từ tầng 1 lên tầng N với chi phí phải trả là ít nhất.
Dữ liệu: Vào từ file văn bản LIFT.INP:
· Dòng
đầu tiên chứa các số nguyên N, U, D, I, J, L.
· Dòng
thứ i trong
số L dòng tiếp theo mô tả hoạt động của thang máy thứ i (i=1,2,...,L): Đầu tiên là số nguyên Ki là số lượng tầng mà thang máy thứ i sẽ dừng, tiếp đến là Ki số nguyên
là chỉ số của các tầng mà thang máy i sẽ dừng (các tầng được sắp xếp theo thứ tự tăng dần của chỉ số).
Hạn chế: 0≤U≤1000, 0≤D≤1000, 0≤I≤1000, 0≤J≤1000, 0≤L≤500,
1≤N≤1000000, 2≤Ki≤1000,
K1+K2+…+KL≤1000.
Kết quả: Ghi ra file văn bản LIFT.OUT một số nguyên là chi phí nhỏ nhất tìm được.
Ví dụ:
|
LIFT.INP
|
LIFT.OUT
|
|
10 1 1 1 1 1
2 3 7
|
7
|
|
LIFT.INP
|
LIFT.OUT
|
|
10 1 1 3 2 1
2 3 7
|
9
|
|
LIFT.INP
|
LIFT.OUT
|
|
20 100 0 1 1 2
2 5 7
2 8 17
|
804
|
