UOJ Logo

NOI.AC

1S 512MB
Statistics

题目描述

小t在学校开了一家餐厅,今天他接到了一笔订单。

某社团订购了n份快餐,每份快餐需要t分钟来制作。

餐厅共有m个厨师,此时每个厨师还需 $a_i$ 分钟可完成手中的任务。小t需要把这n份快餐合理分配给m个厨师,使得大家能够尽快下班。即求一个最小整数T,使得T分钟前所有厨师都能完成自己的全部任务。

为了能尽快下班,所有厨师做完手上的任务后会直接去做小t分配的快餐,中间过程视为无时间损耗。

输入格式

第一行依次为三个整数n,m,t,分别表示某社团订购的快餐数量,餐厅中的厨师人数,制作每份快餐需要消耗的时间,中间用空格隔开。

第二行依次为m个整数,$a_i$表示第i个厨师现有的任务需要消耗的时长。

输出格式

输出一个整数T,表示最快需要多长时间所有厨师能完成全部任务。

输入样例1

5 3 2
3 1 2

输出样例1

6

数据规模与约定

对于$30\%$的数据,$1\le n,m,t,a_i \le 10$.

对于$60\%$的数据,$1\le n,m \le 1000$.

另有$10\%$的数据,保证t=1.

对于$100\%$的数据,$1\le n,m \le 10^5$,$1\le t,a_i \le 1000$.