UOJ Logo

NOI.AC

1S 512MB
统计

题目描述

这天小t又接到了很多笔订单。

此时临近打烊,厨师们纷纷下班,但是仍有n笔订单尚未完成。第i笔订单的制作需要消耗$a_i$的时间。小t可以付m的加班费让一个厨师继续工作T时间(为了符合劳动法,一个厨师最多加班T时间),他想请你帮忙分配任务,使得自己付尽可能少的加班费便可以完成所有订单。

输入格式

第一行输入三个整数n,T,m,表示还需完成的订单数,加班时间,加班费。

第二行依次输入n个整数,$a_i$表示第i笔订单制作消耗的时间。

输出格式

输出一个整数,表示使得所有订单都能被完成的最少的加班费。

输入样例1

5 13 2
6 3 7 4 2

输出样例1

4

数据规模与约定

对于$30\%$的数据,$1\le n \le 8$.

对于$100\%$的数据,$1\le n \le 20$,$1\le a_i,T,m \le 10^8$