Монополія#4846

Монополія

20 секунд
64 мегабайти
Легка

У новій версії гри Монополія гравці можуть об'єднувати кілька бізнесів в один, щоб збільшити свої прибутки. Діють такі правила:

  1. За один хід можна об'єднати рівно два бізнеси в один. Вартість нового бізнесу буде дорівнювати сумі вартостей обох бізнесів до об'єднання.

  2. За кожну операцію об'єднання потрібно сплатити податок у розмірі 5% від сукупної вартості об'єднуваних бізнесів.

Коля заробив багато грошей у грі й тепер хоче об'єднати всі свої бізнеси в один. Він помітив, що загальна сума податку залежить від порядку, в якому об'єднуються бізнеси. Наприклад, у Колі є чотири бізнеси вартістю , , і . Якщо Коля спочатку об'єднає і (сплачуючи податок ), потім результат із (), і нарешті з (), то загалом сплатить . Але якщо він спочатку об'єднає і (), потім і (), а в кінці – два отримані бізнеси (), то заплатить усього лише .

Допоможіть Колі знайти мінімальну суму грошей, яку необхідно витратити для об'єднання всіх його бізнесів у один.

Вхідні дані

Вхідні дані містять один рядок з натуральними числами (2 \leq N \leq 200\,000), кожне не перевищує — вартості бізнесів Колі.

Вихідні дані

Виведіть мінімальну суму грошей, необхідну для об'єднання всіх бізнесів Колі в один.

Приклади

Приклад 1

Loading
Loading