#372. 土拨鼠辰辰的新游戏
土拨鼠辰辰的新游戏
土拨鼠辰辰的新游戏
Background
土拨鼠辰辰迷上了一款叫“炉石传说”的游戏。游戏的玩法很简单,你有n枚硬币,酒馆里有m个随从,每个随从需要k枚硬币,和w[i]的战力值(必须购买,不能买为止)。现在我们要让战力值不超过x,问满足情况的最大的战力值是多少?如果不可以,能么输出No
Description
有m个正整数,从中选n/k个整数,每个正整数的战力值加起来小于等于x的最大值是多少?如果不可以,能么输出No。
Input
第一行四个正整数:n,m,k,x 第2行m个整数
Output
一个整数,表示战力值加起来小于等于x的最大值是多少。如果不可以,能么输出No。
Samples
6 3 3 10
4 7 5
9
6 3 3 100
4 7 5
No
数据范围
1<=n<=10^9; 1<=m<=10^6; 1<=k<=10^4; 1<=x<=10^18; 1<=w[i]<=10^9 n/k<=1e7;