← 返回题目列表

Codeforces · 581/C

C. 发展技能

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

Petya 喜欢电脑游戏。他期待已久的游戏终于出来了!

这个游戏的主角有n个不同的技能,每个技能都用一个0到100的整数ai来表征。ai的数字越大,角色的第i个技能就越高。角色的总评分计算为 $$\left\lfloor \frac{a_i}{10} \right\rfloor$$ 对于从 1 到 n 的所有 i 的值之和。表达式 ⌊ x⌋ 表示将数字 x 向下舍入到最接近的整数的结果。

在游戏开始时,Petya 获得了 k 个改进单位作为奖励,他可以用它来提高角色的技能和总等级。一个改进单位可以将 Petya 角色的任何技能恰好提高 1 个。例如,如果a4=46,则该技能使用1个强化单位后,它就等于47。英雄的技能提升不能超过100。因此,允许部分单位保持未使用状态。

你的任务是确定使用改进单位的最佳方式,以最大化角色的整体评级。没有必要使用所有的改进单元。

输入

输入的第一行包含两个正整数 n 和 k (1 ≤ n ≤ 105, 0 ≤ k ≤ 107) — 角色的技能数量和 Petya 可以使用的改进单位数量。

输入的第二行包含一个由 n 个整数 ai (0 ≤ ai ≤ 100) 组成的序列,其中 ai 表示角色第 i 个技能的等级。

输出

输出的第一行应包含一个非负整数——Petya 使用 k 或更少的改进单位可以获得的角色的最大总评分。

示例

输入 #1

2 4
7 9

输出 #1

2

输入 #2

3 8
17 15 19

输出 #2

5

输入 #3

2 2
99 100

输出 #3

20

注意

在第一个测试用例中,最优策略如下。 Petya必须通过花费3个改进单位将第一个技能提高到10,并通过花费一个改进单位将第二个技能提高到10。因此,Petya 花费了所有的改进单位,角色的总评分等于 lfloor frac{100}{10} rfloor + lfloor frac{100}{10} rfloor = 10 + 10 = 20。

在第二次测试中,Petya 的最佳策略是将第一个技能提高到 20(通过花费 3 个改进单位)并将第三个技能提高到 20(在这种情况下通过花费 1 个改进单位)。因此,Petya 还剩下 4 个改进单位,他将能够将二技能提高到 19(这不会改变总体评分,因此 Petya 不一定必须这样做)。因此,本例中可能的最高总评分为 $$\lfloor \frac { 20 } { 10 } \rfloor + \lfloor \frac { 19 } { 10 } \rfloor + \lfloor \frac { 20 } { 10 } \rfloor = 2 + 1 + 2 = 5$$。

在第三个测试用例中,Petya 的最佳策略是通过花费 1 个改进单位将第一个技能提高到 100。此后,角色的两项技能都将等于 100,因此 Petya 将无法使用剩余的改进单位。所以答案等于 $$\lfloor \frac { 100 } { 10 } \rfloor + \lfloor \frac { 100 } { 10 } \rfloor = 10 + 10 = 20$$。