Корупція

prb21 З метою боротьби з тіньовою економікою банк запровадив об’єднання N рахунків фірми в один. За одну операцію об’єднуються 2 рахунки і банк автоматично відраховує на власний рахунок Р% від суми об’єднання за виконання операції та закриття одного з рахунків. Яка найбільша кількість коштів може залишитись на рахунку фірми? На кожному з рахунків до впровадження політики об’єднання було не більше ніж G грн.

Технічні умови

Вхідні дані

У першому рядку 2 числа: кількість рахунків та процент відрахування.

У другому рядку N чисел: сума на кажному з рахунків фірми.

Вихідні дані

Найбільша сума, що може залишитись на рахунку.

2 ≤ N ≤ 100000

0 ≤ Р ≤ 20

0 ≤ G ≤ 10000

Інформація про задачу

Ліміт часу: 1 секунда
Ліміт пам`яті: 64 MB
Бали за пройдений тест: 7.5
Складність: 93% 12/177
Класифікація: Жадний алгоритм

Приклад

Приклад вхідних даних

4 5
1000 1100 1200 1300

Приклад вихідних даних

4151.50

← Скільки можна?

Список задач