思路概述

击败第 i 只怪物的额外加成只与“已击败数量对 10 取模”有关，而与具体击败了谁、击败了多少整十无关。因此可用动态规划，把“已击败数量 mod 10”作为状态，线性推进。

状态设计

令 dp[m] 表示在处理完当前怪物之前，已击败数量 ≡ m (mod 10) 时能获得的最大经验值（滚动数组维护上一只怪物处理后的状态）。

转移

题目内容

小美会按照编号从小到大的顺序依次遇到 $n$ 只怪物（编号为 $1$ ~ $n$），怪物 $i(1 ≤ i ≤ n)$ 的生命为 $a_i$ 。

对于每只怪物，小美都可以选择放走 Ta 或者击败 Ta。

• 如果放走怪物，小美将获得 $i$ 点经验值。

• 如果击败怪物，小美将获得 $a_i$ 点经验值，同时将额外获得 ($x$ $mod$ $10) × a_i$ 点经验值，$x$ 为击败怪物数量（包括这一个怪物）。

求小美最多可以从这 $n$ 个怪物中获得的经验值。

输入描述

第一行输入一个整数 $n(1 ≤ n ≤ 2 × 10^5)$ 表示怪物数。

第二行输入 $n$ 个整数 $a_i(1 ≤ a_i ≤ 10^9)$ 表示怪物的生命。

输出描述

输出一个整数表示小美可以获得最高的经验值。

样例1

输入

3
5 3 2

输出

27

说明

第一个怪物选择击败获得 $5+5×1= 10$ 的经验值，第二个怪物选择击败获得 $3+3×2= 9$ 的经验值，第三只怪物选择击败获得 $2+ 2×3=8$ 的经验值，总共获得 $27$ 的经验值。