Магічні палиці#2287
Магія розглядалася давніми народами як засіб отримати допомогу від божественних сил. Відомий випадок, коли група чаклунів кинула свої жезли на землю, і ті дивовижним чином перетворилися на живих змій. У відповідь інша людина кинула свій жезл, який перетворився на змію, що пожерла змій чаклунів!
Єдина магія, яка вам знадобиться у цій задачі, — це розв'язати її. Вам дано чарівну паличку, що складається з кількох прямих відрізків, з'єднаних шарнірами, які дозволяють згинати паличку. Залежно від довжин відрізків і способу їх складання можна отримувати різноманітні багатокутники. Вам потрібно визначити максимальну площу, яку можна обмежити багатокутниками, утвореними згинанням палички таким чином. Кожен відрізок може входити не більше ніж в один багатокутник. Відрізки можуть стикатись лише своїми кінцями. Наприклад, паличка, зображена нижче, складається з п'яти відрізків і чотирьох шарнірів і може бути складена у багатокутник, показаний праворуч.
Вхід містить декілька тестових випадків. Кожен тестовий випадок описує чарівну паличку. У першому рядку кожного тесту знаходиться число відрізків (1 \le n \le 500) у чарівній паличці. У наступному рядку розміщено цілих чисел S_1, S_2, \ldots, S_n (1 \le S_i \le 1000) — довжини відрізків у порядку, як вони з'являються у паличці.
Після останнього тесту іде рядок, що містить одне число .
Для кожного тесту виведіть його номер і максимальну можливу площу замкненого контуру, яку можна отримати складанням чарівної палички у відповідних місцях. Відповіді з абсолютною або відносною похибкою не більше 10^{-4} вважаються правильними.
Формат виводу показано у прикладі.
Приклад 1