Миша купил себе новый электромобиль и использует его каждый день для перемещения по городу. Поскольку Миша старается не перенапрягаться, каждый день он ездит только на одну из двух работ.
День Миши начинается с того, что он заряжает с утра электромобиль ровно настолько, чтобы ему хватило заряда для поездки на день. Если Миша едет на первую работу, стоимость зарядки составляет 1000 бурлей, а если на вторую, то 2000 бурлей.
На зарядной станции, где заряжается Миша, действует система бонусных карт. На бонусной карте может находиться некоторое неотрицательное количество бонусных бурлей. Каждый раз, когда покупатель оплачивает покупку стоимостью x бурлей, он может любую часть стоимости покупки в y (0 ≤ y ≤ x) бурлей, которая не превосходит баланса на бонусной карте, оплатить бонусными бурлями. В таком случае он платит x - y бурлей наличными, а сумма на бонусной карте уменьшается на y бонусных бурлей.
А если покупатель полностью расплатился наличными (то есть, y = 0), то 10% от суммы покупки возвращается на бонусную карту, то есть, счёт на бонусной карте увеличится на 
бонусных бурлей. Изначально баланс карты составляет 0 бонусных бурлей.
Миша распланировал первые n дней пользования картой и знает, сколько стоит зарядка в каждый из этих дней. Помогите Мише определить какое минимальное количество бурлей ему придётся потратить наличными при оптимальном использовании бонусной карты. Считайте, что Миша в состоянии в любой день оплатить любую часть стоимости наличными. Тратить все бонусные бурли с бонусной карты к концу рассматриваемого периода не обязательно.
В первой строке находится целое число n (1 ≤ n ≤ 300 000) — число дней, которые распланировал Миша.
В следующей строке содержатся n чисел a1, a2, ..., an (ai = 1000 или ai = 2000), где ai обозначает стоимость зарядки в i-й день.
Выведите единственное число — ответ на задачу.
3
1000 2000 1000
3700
6
2000 2000 2000 2000 2000 1000
10000
В первом тестовом примере Мише выгодно заплатить за первые два дня наличными, потратив 3000 бурлей, и получить 300 бонусных бурлей. После этого он может заплатить только 700 бурлей за третий день, покрыв оставшуюся часть стоимости бонусными бурлями.
Во втором тестовом примере Мише выгодно первые пять дней платить полную стоимость, в результате чего накопить 1000 бонусных бурлей, которыми можно расплатиться в последний день, ничего не доплачивая.
