迈克尔刚刚购买了一辆新电动汽车,用于在城市中行驶。迈克尔不喜欢过度工作,因此每天他只开车去两份工作中的一份。
迈克尔的一天从为上下班的电动车充电开始。如果他去第一份工作,他要花 1000 伯尔的费用;如果他去第二份工作,他要花 2000 伯尔的费用。
在他使用的充电站上有一个涉及奖励卡的忠诚度计划。奖励卡可能有一些非负金额的奖励毛刺。每次顾客打算以 x burles 的价格购买商品时,他可以支付 y (0 ≤ y ≤ x) burles 的金额,该金额不超过奖励 burles 的奖励卡余额。在这种情况下,他用现金支付 x - y burles,并且奖金卡上的余额减少 y 奖金 burles。
如果客户用现金支付全价(即 y = 0),则 10% 的价格将返还至奖励卡。这意味着奖金卡余额增加 $$\frac{\pi}{10}$$ 奖金 burles。最初,奖金卡余额等于 0 奖金 burles。
Michael 计划了接下来的 n 天,并且他知道每一天的费用是多少。帮助迈克尔确定他必须花费的最低现金金额,并最佳使用奖励卡。假设迈克尔能够在任何一天用现金支付任何部分的价格。没有必要在给定期限结束时花完所有奖金。
输入
输入的第一行包含一个整数 n (1 ≤ n ≤ 300 000),即 Michael 计划的天数。
下一行包含 n 个整数 a1, a2, ..., an(ai = 1000 或 ai = 2000),其中 ai 表示第 i 天的充电费用。
输出
输出 Michael 必须花费的最少 burles 数量。
示例
输入 #1
3 1000 2000 1000
输出 #1
3700
输入 #2
6 2000 2000 2000 2000 2000 1000
输出 #2
10000
注意
在第一个示例案例中,Michael 的最佳方式是支付前两天花费 3000 burles 的费用,并获得 300 burles 奖励作为回报。此后,他只能支付第三天的 700 伯勒,并用奖金伯勒支付剩余的费用。
在第二个示例案例中,Michael 的最佳方式是支付前五天的全部费用,获得 1000 个奖励 burles 作为回报,并可以在最后一天使用它们,而无需支付任何现金。