Magachip IV the Splendid, vua của Byteotia, có ý định chọn phò mã cho công chúa Ada của mình. Công chúa thì muốn chồng mình phải là người thông minh, không keo kiệt và không lãng phí quá. Nên nhà vua suy nghĩ mới chọn phương pháp thử tài bằng cách chọn lâu đài của mình làm nơi thi đấu. Lâu đài gồm nhiều phòng trưng bày đồ quí hiếm và nối với nhau bằng dãy các hành lang để thần dân có thể tham quan, phòng cuối cùng là phòng của công chúa, để thăm một phòng phải trả một đồng bytealer và sẽ xuất phát từ phòng đầu tiên. Nhà vua trao cho mỗi chàng trai đến cầu hôn một số đồng tiền chứa trong 1 cái túi và yêu cầu là mỗi người thăm 1 số phòng sao cho đến phòng cuối cùng thì tiêu hết số tiền đã cho, nếu đến phòng cuối cùng mà vẫn còn tiền thì phải thăm lại một số phòng

trưng bày nữa mới quay lại. Hãy lập trình giải quyết vấn đề trên để 1 chàng trai luôn có

thể thực hiện được yêu cầu của nhà vua.

Dữ liệu nhập từ file Zam.inp miêu tả lâu đài, số hiệu phòng công chúa đang ở, tổng số tiền trong túi:

-          Dòng đầu tiên có 5 số nguyên dương n(số lượng phòng), m(số hành lang), e(số hiệu phòng xuất phát), p(số hiệu phòng công chúa), b(tổng số tiền vua ban cho).

-          Dòng  2 có n số nguyên dương c_i, mỗi số là chi phí mỗi lần vào thăm trong phòng i.

-          Trong m dòng tiếp theo có từng cặp số nguyên dương (x, y), mỗi cặp nối biểu thị một hành lang nối phòng x với phòng y.

 Tính ra dãy các phòng đi qua đến phòng của công chúa và lưu hành trình vào file Zam.out