5604: 【贪心】字节跳动2024秋招-小U的购物策略
金币值：
1
时间限制：4.000 s
内存限制：128 M
正确：5
提交：14
正确率：35.71% 命题人：
题目描述
小U有n个钱包，每个钱包中装有不同数量的现金，表示为a_i元。
小U计划每天使用一个钱包的全部金额购买单价为k元的商品。
在开始购物之前，小U可以选择性地向一些钱包中加入更多的钱，但总额不能超过m元。
小U希望制定一个最优策略，使得他能够购买最多数量的商品。
现在他想知道，在最优策略下，他最多能购买多少件该商品。
输入格式
首先输入一行包含三个整数n,k,m，分别代表钱包的数量，商品的单价，以及小U最多可以加入钱包中的钱的总额。
接下来的一行输入n个正整数a_1,a_2,...,a_i，分别代表每个钱包中的初始金额。
1 <= n <= 10^5
1 <= k <= 10^9
0 <= m <= 10^14
1 <= a_i <= 10^9
输出格式
输出一个整数，表示小U在最优策略下最多能购买的商品数量。
输入样例 复制
5 3 2
4 4 3 1 2输出样例 复制
4