题目内容

某个服务器集群接收了一批共 $n$ 个计算任务，其中第 $i$ 个任务需要 $tasks[i]$ 单位的总计算量。系统必须在 $h$ 小时内将这些任务全部处理完毕。你需要确定同时运行的服务器数量 $k$。

系统以整小时为单位进行调度。每台服务器每小时最多完成 1 单位计算量。调度必须满足以下规则：

• 同一小时内，所有服务器只能共同处理同一个任务，不能拆分到多个任务上。
• 集中处理：每个小时开始时，需要选择一个尚未完成的任务，并将全部 $k$ 台服务器都分配给该任务。若该任务剩余计算量大于或等于 $k$，则这个小时内会消耗该任务 $k$ 单位计算量；若小于 $k$，则该小时结束时该任务完成。
• 资源闲置：如果被选中任务的剩余计算量小于 $k$，多出的服务器在这个小时内不会被用于其他任务，而是处于闲置状态。

请计算在 $h$ 小时内完成全部任务所需的最少同时运行服务器数量。如果不存在可行的服务器数量，输出 -1。

约束条件：

• 任务数量 $n$ 介于 1 和 1000 之间。
• 每个任务计算量 $tasks[i]$ 介于 1 和 1000007 之间。
• 截止小时数 $h$ 介于 1 和 1000007 之间。

输入描述

第一行包含一个整数 $n$，表示任务数量。

第二行包含 $n$ 个正整数，依次为 $tasks[0], tasks[1], \ldots, tasks[n-1]$，表示每个任务的总计算量。

第三行包含一个整数 $h$，表示完成所有任务的截止小时数。

输出描述

输出一个整数，表示在 $h$ 小时内完成全部任务所需的最少同时运行服务器数量。

如果没有任何可行方案，则输出 -1。

样例1

输入

3
3 5 7
5

输出

4

说明

当 $k=3$ 时，任务 3、5、7 分别需要 $\lceil 3/3\rceil=1$、$\lceil 5/3\rceil=2$、$\lceil 7/3\rceil=3$ 小时，总计 $1+2+3=6$，超过截止时间 5 小时。

当 $k=4$ 时，三个任务分别需要 $1$、$2$、$2$ 小时，总计 $1+2+2=5$，刚好满足截止时间。

因此最少需要 4 台服务器。

样例2

输入

4
10 10 10 10
3

输出

-1

说明

共有 4 个任务。无论同时运行多少台服务器，同一小时内所有服务器只能共同处理同一个任务，因此每个任务至少要占用 1 小时。

所以完成所有任务至少需要 4 小时，而截止时间只有 3 小时，无法完成，输出 -1。

样例3

输入

1
1000007
1

输出

1000007

说明

只有 1 个任务，计算量为 1000007。截止时间也是 1 小时，因此所有计算量必须在这 1 小时内完成。

每小时每台服务器最多处理 1 单位计算量，所以至少需要 1000007 台服务器。

最少服务器数量为 1000007。

样例4

输入

5
2 3 1 4 5
14

输出

2

说明

使用 1 台服务器时，总耗时为所有任务计算量之和，即 $2+3+1+4+5=15$，超过截止时间 14 小时。

使用 2 台服务器时，各任务耗时分别为 $\lceil 2/2\rceil=1$、$\lceil 3/2\rceil=2$、$\lceil 1/2\rceil=1$、$\lceil 4/2\rceil=2$、$\lceil 5/2\rceil=3$，总耗时为 $1+2+1+2+3=9$，不超过 14 小时。

因此最少需要 2 台服务器。