← 返回题目列表

Codeforces · 853/D

D. 迈克尔和充电站

中文机器翻译题面 查看原题

迈克尔刚刚购买了一辆新电动汽车,用于在城市中行驶。迈克尔不喜欢过度工作,因此每天他只开车去两份工作中的一份。

迈克尔的一天从为上下班的电动车充电开始。如果他去第一份工作,他要花 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 作为回报,并可以在最后一天使用它们,而无需支付任何现金。