LUNARNY - Đi chơi Tết
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 3.0 giây
Giới hạn bộ nhớ: 256 megabyte
Đăng bởi: mrtan_lovelife

Nhân dịp Tết Nguyên Đán, Misaki cùng các bạn của mình lại tổ chức một cuộc vui chơi ở khu vui chơi giải trí giống như đợt đi chơi Halloween vừa rồi. Nhắc lại bài toán: Nhà của Misaki và các bạn của cô nằm trên cùng 1 con đường, các nhà được đánh vị trí từ 1 đến N, mỗi nhà cách nhau 1 mét. Nhà của Misaki ở vị trí 1 và khu vui chơi ở vị trí N. Nhà M người bạn của Misaki ở các vị trí a1, a2,..., aM. Ngoài ra trên tuyến đường còn có P trạm xe buýt tại các vị trí b1, b2, ..., bP. Từ nhà mình, Misaki sẽ đi đến nhà của các bạn mình. Cô có thể đi bằng taxi hoặc xe buýt. Với taxi, cô có thể bắt từ bất kì vị trí nào, giá của taxi là T đồng/mét. Với xe buýt, cô chỉ có thể bắt từ trạm này và đi đến một trạm khác, giá của xe buýt là B đồng/lượt không phân biệt khoảng cách. Tuy rằng trong túi đang rủng rỉnh tiền lì xì nhưng Misaki vẫn phải tìm cách đi tiết kiệm tiền nhất sao cho thăm đủ tất cả các bạn và đến khu giải trí N để chơi được nhiều trò chơi hơn. Sau khi nghe kể về chuyến đi chơi Halloween, thầy Admin đã gợi ý Misaki rằng cô nên thăm nhà các bạn theo thứ tự bất kì để tiết kiệm được nhiều tiền nhất. Bạn hãy giúp Misaki tìm cách đi đón tất cả các bạn và đến điểm vui chơi với số tiền phải trả là ít nhất nhé! wink

Yêu cầu: Cho biết số nhà trên đường, các nhà phải đến đón, số trạm xe buýt và số tiền đi xe taxi, xe buýt, bạn hãy tìm cách đi sao cho đến thăm tất cả các nhà và đến vị trí N với số tiền ít nhất.

Dữ liệu nhập: 

  - Dòng thứ nhất chứa các số nguyên N, M, P, T, B là số nhà, các nhà phải đón, số trạm xe buýt và số tiền đi taxi, xe buýt. (1 ≤ N ≤ 109 | 0 ≤ M ≤ 20 | 0 ≤ P ≤ 1000 | 1 ≤ T,B ≤ 104).

  - Dòng thứ hai chứa M số nguyên là các nhà phải đến, số thứ alà vị trí của nhà thứ i (1 ≤ a≤ N). Dữ liệu cho đảm bảo không có 2 nhà trùng vị trí.

  - Dòng cuối cùng chứa P số nguyên là vị trí các trạm xe buýt theo thứ tự tăng dần, số thứ bi là vị trí của trạm thứ i, mặc định có trạm ở vị trí 1 và N. (1 ≤ b≤ N).

Dữ liệu xuất:

  - Dòng thứ nhất chứa 1 số nguyên duy nhất là số tiền ít nhất phải trả.

  - Dòng thứ hai chứa M số nguyên là thứ tự Misaki thăm nhà các bạn của mình. Nếu có nhiều đáp án, chỉ cần in ra 1 cách đi bất kì.

Ví dụ

  • input
    10 2 2 1000 2000
    5 8
    4 7
    output
    8000
    1 2

- Đầu tiên Misaki đi xe buýt từ 1 đến 4 

- Sau đó đi taxi từ 4 đến 5, 5 đến 8 và 8 đến 10

Tổng số tiền là 2000+1000+3000+2000=8000 đồng

Back to Top