В Екатеринбурге всего одна линия метро. Но какая! Каждая станция — настоящий архитектурный шедевр. Неудивительно поэтому, что все гости города стараются успеть осмотреть наш метрополитен поподробнее. И, как всегда, туристы стремятся уложиться в минимально возможное время — они ведь столько должны успеть! В целях повышения туристической привлекательности Екатеринбурга, администрация города решила создать программу, которая рассчитывала бы оптимальный с точки зрения времени обзорный маршрут по всем станциям города. Конечно, оборот «администрация города решила создать программу» не вполне точно отражает суть ситуации — администрация города решила, а создать программу придется вашей команде.

Метро состоит из одной линии. Поезда ходят по этой линии с определенным интервалом, который выражается целыми минутами, известны также интервалы между станциями (которые также составляют целые минуты). Стоянку поезда на станции можно считать мгновенной. Выход из поезда турист производит также мгновенно, посадка в поезд занимает одну секунду, а на полный осмотр всех архитектурных достоинств станции туристу надо 58 секунд. Осмотрев все станции, турист должен вернуться на ту, с которой он начинает свой путь. Эта станция, конечно же, считается осмотренной в начальный момент времени и время ее осмотра не надо включать в общую продолжительность поездки. Начать осмотр станций турист может в наиболее удобный для этого момент времени, поэтому общую продолжительность поездки следует отсчитывать от момента посадки туриста в поезд метро на станции отправления.

В первой строке указано количество станций N (1 ≤ N ≤ 16). Станции нумеруются от 1 до N. Во второй строке указано N − 1 неотрицательное, не превышающее 10⁵ число минут — время следования состава между станциям, с 1 до 2, со 2 до 3, и т.д. (конечно, с i-й станции на (i+1)-ю поезд едет ровно столько же минут, сколько с (i+1)-й на i-ю). В третьей строке — номер станции, с которой турист начинает «объезд» станций. В четвёртой — три числа: интервал следования поездов, время отправки первого поезда со станции 1, время отправки первого поезда со станции N, все числа неотрицательные целые, имеют размерность минут. Интервал движения не равен 0 и не превышает 10⁵, а времена отправки поездов с конечных станций не превышают интервала.

Следует вывести единственное целое число — продолжительность кратчайшего возможного осмотра всех станций в минутах.