3189. [SYOI 2019] YH准备

【题目背景】

  两年前的这个时候，YH教成立了。

  YH教一经成立，响应者无数，由于正义的教义，理性的认知，光明的向往，YH教创立不久，便通过了联禾国第6666号议案，YH教成为世界第四大中教。

  YH教成员都有着共同的信念，要成为集美貌与智慧，感性与理智于一身的ZYH，而只要成为YH教的成员，你，便是YH！！！

  可是，在追寻信仰的过程中总有坎坷与辛酸，在YH教中亦是如此，ZYF就是这条道路上的艰难险阻，他会阻止任何YH教成员达到最终信仰。但无可否认的是，正因为ZYF的存在，YH教的道路上才有滋有味，丰富多彩。

  所以，YF也就成为了YH教的吉祥物。

  而你是否有动心，要来参加这YH教创立两周年庆典，成为YH教的一员。

  今天是YH教创立两周年庆典，每一位YH都会来庆祝这一重要的日子，当然吉祥物YF也要来参加，毕竟他的任务就是要阻止YH的快乐生活。

  YF要好好准备一下，该带些什么武器去参加这“快乐的聚会”。他需要十分认真地分配一下自己的武器，虽然他想把自己所有的武器都带上，可是根据事实情况，这并不允许，毕竟YF的武器太多了，70m长的大砍刀，意大利炮，社会主义铁拳，资本主义中指，死神诅咒所需要的祭坛，野猪冲锋所需要的跑鞋，嘴炮攻击需要的纸巾等等等等.

  可是由于ZYF太笨了，他并不知道该如何分配自己的背包容积，他希望请你这位YH帮忙，他答应你在庆典的时候打你会轻一点，保证你能够活着回家，不会像其他人一样“惨死”在庆典上，你毫不犹豫地同意了他的请求，毕竟你可不想成为YH仅仅一天就死在YF的手上。

  毕竟你是YH，你依旧是YF的仇敌，他会给你不合理的限制，但为了最终信仰，你不得不都满足他了。

【题目描述】

  YF有一个背包容积为$M$的超大背包，准备分配给自己的$N$种武器。

  每种武器有无限个，每一个武器的体积均为$1$。

  每一种武器有一个武力值，第i种武器的武力值为$w[i]$；

  而如果有$a[i]$种武器拿的个数比第i种武器拿的多，那么对于第$i$种武器，YF会产生 $w[i]*a[i]$ 的怒气值。

  YF要求你，告诉你$N,M,$和序列$w$，你需要求出对于每一种武器，该如何安排每一种武器的个数，使每一种武器至少拿一个，且使YF的怒气值最低，求出最小怒气值即可。

【输入格式】

  第一行两个整数，$N，M $表示武器个数，背包容积

  第二行 $N$ 个整数， $w1,w2,w3,w4······wn $表示 $N$ 种武器的武力值。

【输出格式】

  一个整数，表示最小的怒气值。

【样例输入】

3 20
1 2 3

【样例输出】

2

【提示】

对于 50% 的数据： 1<=N<=10 1<=M<=50 1<=w<=100

对于 80% 的数据： 1<=N<=30 1<=M<=5000 1<=w<=1e7

对于 100% 的数据： 1<=N<=150 1<=M<=5000 1<=w<=1e7

【来源】

LGLJ