codeforces581C

Developing Skills

 CodeForces - 581C 

你在玩一个游戏.
你操作的角色有n个技能,每个技能都有一个等级ai.
现在你有k次提升技能的机会(将其中某个技能提升一个等级,可以重复提升某一个等级).
但技能的等级不能超过100.
你可以不用用完全部的k次机会.
已知角色的能力值=∑(ai/10),其中除法为向下取整的整除运算.
问你如何分配这k次机会,才能使得角色的能力值最高.
输出这个最大的能力值.

Input

第一行两个整数n,k(1<=n<=10^5,0<=k<=10^7).
第二行有n个整数ai(0<=ai<=100).
Output

输出只有一个整数,表示最大的能力值.

Examples

Input

2 4
7 9

Output

2

Input

3 8
17 15 19

Output

5

sol：此题和492C有异曲同工之妙，开一个系统堆，重载运算符为%10尽量大即可，反复做直到全部都是100级或者机会没了

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read()
{
    ll s=0;
    bool f=0;
    char ch=' ';
    while(!isdigit(ch))
    {
        f|=(ch=='-'); ch=getchar();
    }
    while(isdigit(ch))
    {
        s=(s<<3)+(s<<1)+(ch^48); ch=getchar();
    }
    return (f)?(-s):(s);
}
#define R(x) x=read()
inline void write(ll x)
{
    if(x<0)
    {
        putchar('-'); x=-x;
    }
    if(x<10)
    {
        putchar(x+'0');    return;
    }
    write(x/10);
    putchar((x%10)+'0');
    return;
}
#define W(x) write(x),putchar(' ')
#define Wl(x) write(x),putchar('
')
const int N=100005;
ll n,Up,Yaoq;
struct Fens
{
    ll a,b;
}Score[N];
inline bool cmp_b(Fens p,Fens q)
{
    return p.b<q.b;
}
int main()
{
    int i;
    ll Sum=0,ans=0;
    R(n); R(Up); R(Yaoq);
    for(i=1;i<=n;i++)
    {
        R(Score[i].a); R(Score[i].b);
        Sum+=1ll*Score[i].a;
    }
    sort(Score+1,Score+n+1,cmp_b);
    i=0;
    while(Sum<1ll*n*Yaoq)
    {
        ll oo=min(1ll*(Up-Score[++i].a),1ll*(1ll*n*Yaoq-Sum));
        Sum+=1ll*oo;
        ans+=1ll*oo*Score[i].b;
    }
    Wl(ans);
    return 0;
}
/*
input
5 5 4
5 2
4 7
3 1
3 2
2 5
output
4

input
2 5 4
5 2
5 2
output
0
*/