Задача E2. Island cafe ≡

Условие

Юный программист Вася живёт на острове и каждый день обедает в кафе около своего дома. Являясь постоянным посетителем, Вася хочет поучаствовать в бонусной программе данного кафе. Прежде чем это сделать, он хочет оценить выгоду, которую мог бы получить, если бы пользовался бонусами последние N дней.

В i-й день Вася тратил на обед в кафе a_i монет. По условиям программы, он мог либо накопить ⌊ 0.01 ⋅ a_i⌋ от суммы обеда в виде бонусов, либо оплатить до ⌊ 0.5 ⋅ a_i⌋ бонусами, которые у него есть.

Помогите Васе узнать, какую максимальную сумму денег он мог бы сэкономить, пользуясь бонусами в течение N дней.

Формат входных данных

Первая строка содержит целое число N — количество дней.

Вторая строка содержит N целых чисел a_i, разделенных пробелом — количество монет, которые тратил Вася на обед в i-й день.

Формат выходных данных

Выведите единственное целое число — количество монет, которые Вася мог бы сэкономить пользуясь бонусной программой.

Ограничения

1 ≤ N ≤ 10³

1 ≤ a_i ≤ 10⁴

Примеры тестов

2
1000 20

10

3
100 1000 1000

11