#2482. 最小分段数

最小分段数

Description

姚耀想聘请mm 个人,有nn 个人前来面试。姚耀决定为这项任务选择mm 个面试官。首先,他将面试者按到来的顺序分成mm 段,每段的长度都是 nm\lfloor\frac{n}{m} \rfloor,这意味着他忽略了来晚的面试者。然后将每段都分配给面试官,面试官从他们中选择最好的一个作为雇员。每个面试者都有一个能力值,能力值越高越好。姚耀希望尽可能减少雇员,且员工的能力值总和大于kk 。请帮他找到最小的mm

Input

输入包含多个测试用例。

每个测试用例的第1行都包含两个数字nnkk ,表示面试的人数和姚耀想聘用的员工能力值之和;

22行都包含nn 个数字v1,v2,,vv _1 , v _2 , …, v,分别表示每个面试者的能力值。

以两个1-1结束,不处理。

数据范围:n200000k1000000000,0vi1000n≤200000,k ≤1000000000,0≤v_i ≤1000。

Output

对每个测试用例,都单行输出可以找到的最小mm 。若找不到,则输出1-1

Samples

11 300
7 100 7 101 100 100 9 100 100 110 110
-1 -1
3

来源

HDU3486