Statement

Elia wanted to go to Ireland, however due to a distraction he boarded the wrong flight and found himself stranded in Lublin. He quickly booked a room in a local hotel, and now has to reach it in the cold night. His hotel is located at the end of a N meter long street. Along the street there are N-1 clothes shops, the i-th of which is located i meters from the airport. Elia only moves towards the hotel and when he passes in front of the i-th shop he can choose whether: (1) keep going without entering; (2) enter the shop paying 1 złoty and buy nothing; (3) enter the shop paying 1 złoty and buy an additional layer of clothes for A_i złotych. However, he wants to avoid walking more meters without entering a shop than he wears layers of clothes, to avoid getting too cold. Knowing Elia only wears a single layer of clothes when he arrives at the airport, what's the minimum he has to spend to reach the hotel?