G — Hídautomatizálás

Delftben még mindig számos olyan híd van, amelyet egy ember, a hídoperátor működtet. Az egyik ilyen hídoperátor hamarosan nyugdíjba megy, ezért szükség van a helyettesítésére. A Bridzs és Poker Bizottság úgy döntött, hogy egy számítógépes programot fognak használni a híd automatikus nyitására és zárására, ezzel szükségtelenné téve az emberi beavatkozást.

Ezt a programot azonban még meg is kell írni. A projekt követelményei az alábbiak:

Egyetlen hajót sem szabad 30 percnél hosszabb ideig várakoztatni.
Azt az időtartamot, amíg a híd nem elérhető a közúti forgalom számára, a lehető legkisebb értéken kell tartani az 1. követelmény betartása mellett.

A híd felhúzása és leengedése 60 másodpercet vesz igénybe. Ez alatt az idő alatt a híd nem elérhető sem a közúti, sem a vízi forgalom számára.

A hajók előre megjósolható időben érkeznek a hídhoz. Minden hajónak 20 másodperc szükséges a híd keresztezéséhez, feltéve hogy a híd már teljesen fel van húzva.

Ha a híd még nincs teljesen felhúzva, amikor odaér egy hajó, akkor a hajónak várakoznia kell. Ha vannak várakozó hajók, amikor a híd teljesen kinyílik, akkor a hajók egyesével keresztezik a hidat, és ez hajónként 20 másodpercet vesz igénybe. A hídnak teljesen nyitva kell maradnia mindaddig, amíg vannak keresztező hajók! Miután minden hajó elment, a hidat le lehet engedni. Elképzelhető azonban, hogy érdemes egy kicsit tovább nyitva tartani a hidat, ha a következő hajó hamarosan megérkezik.

Az összes hajó érkezési idejének ismeretében úgy kell működtetni a hidat, hogy minden hajó át tudjon menni anélkül, hogy bármelyiknek is 30 percnél hosszabb ideig kellene várakoznia. Mekkora az az összidőtartam, amíg a híd nem elérhető a közúti forgalom számára?

A bemenet specifikációja

A bemenet első sora egy N egész számot tartalmaz, amely a hidat keresztezni szándékozó hajók számát adja meg (1 ≤ N ≤ 4000).

Ezt N sor követi, amelyek mindegyikében egy T_i egész szám szerepel, amely azt az időpontot jelzi másodpercben, amikor az i-edik hajó a hídhoz ér (60 ≤ T_i ≤ 10⁵).

A hajók az érkezési idők növekvő sorrendjében lesznek megadva, és sosem érkeznek 20 másodpercen belül egymáshoz képest (azaz i < j esetén T_i + 20 ≤ T_j teljesül).

A kimenet specifikációja

A kiemenetre egyetlen sort kell kiírni egy egész számmal, amely azt a minimális összidőtartamot adja meg másodpercben, ameddig a hidat le kell zárni a közúti forgalom elől, hogy minden hajó áthaladhasson rajta.