Кіріс файлының атауы: input.txt Шығу файлының атауы:output.txt Уақыт шектеулері: 2 секунд Жад шектеулері: 256 Мб Берік көлікпен саяхаттағанды жақсы көреді. Ол өзі үшін А нүктесінен В нүктесіне дейінгі маршруттың картасын жасады. Алайда жолда тас жолдағы ақауларды азайту үшін көлікке техникалық қызмет көрсету қажет, сондықтан ол бірінен соң бірі орналасқан N техникалық қызмет көрсету пункті бар бағытты таңдады. і (1 ≤ N) нөмірі нүктесінде автомобильге қызмет көрсету құны Аі тең. Берік қатарынан 3 пункттен аспайтын қызмет көрсетусіз жүре алады. Бұл жағдайда автомобиль кем дегенде 1 рет техникалық қызмет көрсетуден өтуі керек. Беріктің маршрут бойымен жүргенде көлікке қызмет көрсетуге жұмсайтын ең аз соманы анықтаңыз. Еңгізу деректердің форматы Енгізу файлының бірінші N (1 ≤ N ≤ 1000) мәні және келесі N жолдардың әрқайсысында Аі мәні бар (109-дан аспайтын оң бүтін сан). Шығыс деректердің форматы Шығару файлының жалғыз жолында автокөлікке техникалық қызмет көрсетуге жұмсалатын ақшаның қажетті сомасы көрсетіледі. Еңгізу және шығару деректерінің мысалы Еңгізу деректері 7 3 4 5 10 3 12 8 Шығару деректері 6 Тусініктемелер. Беріктің күтімі 1 және 5 пункттерде жасалуы керек.