Sehrli çubuqlar#2287
Sehr qədim xalqlar magiyanı ilahi qüvvələrin köməyini əldə etmək üçün bir vasitə kimi qəbul edirdilər. Məşhur bir hekayədə bir qrup sehrbaz çubuqlarını yerə atır və onlar möcüzəvi şəkildə canlı ilanlara çevrilir. Cavab olaraq, başqa bir şəxs yerə bir çubuq atır, o da ilana çevrilir və sehrbazların ilanlarını məhv edir!
Bu tapşırıq üçün lazım olan tək sehr onun həllidir. Sizin bir neçə düz seqmentdən və qatlanmağa imkan verən menteşələrdən ibarət sehrli çubuğunuz var. Seqmentlərin uzunluğuna və onların qatlanma üsuluna görə müxtəlif sayda çoxbucaqlar əldə etmək mümkündür. Siz bu şəkildə əmələ gələn çoxbucaqların məhdudlaşdıra biləcəyi maksimum sahəni tapmalısınız. Hər bir seqment yalnız bir çoxbucağa daxil olmalıdır. Seqmentlər yalnız ucları ilə toxuna bilər. Məsələn, aşağıda göstərilən çubuq beş seqment və dörd menteşədən ibarətdir. O, sağdakı şəkildə göstərilən çoxbucağı əldə etmək üçün qatlana bilər.
Giriş bir neçə test tapşırığından ibarətdir. Hər bir test bir sehrli çubuğu təsvir edir. Testin ilk sətirində sehrli çubuqdakı seqmentlərin sayı (1 \le n \le 500) verilir. Növbəti sətirdə çubuqdakı seqmentlərin yerləşmə sırasına uyğun olaraq tam ədəd S_1, S_2, \ldots, S_n (1 \le S_i \le 1000) – seqmentlərin uzunluqları verilir.
Son testdən sonra tək sıfırdan ibarət bir sətir gəlir.
Hər test üçün nömrəsini və çubuğu verilmiş yerlərdə qatlayaraq əldə edilə bilən qapalı sahənin maksimum mümkün sahəsini çap edin. Cavablar üçün 10^{-4}-dən çox olmayan mütləq və ya nisbi səhvlər qəbul olunur.
Çıxış formatı nümunədə göstərilmişdir.
Nümunə 1