部门在进行需求开发时需要进行人力安排。当前部门需要完成 N 个需求,需求用 requirements 表示,requirements[i] 表示第 i 个需求的工作量大小,单位为人月。这部分需求需要在 M 个月内完成开发。进行人力安排后,每个月的人力是固定的。要求每个月最多有 2 个需求开发,并且每个月需要完成的需求总工作量不能超过部门的人力。
请帮助部门评估在满足需求开发进度的情况下,每个月需要的最小人力是多少。
部门在进行需求开发时需要进行人力安排。
当前部门需要完成 N 个需求,需求用 requirements 表述,requirements[i] 表示第 i 个需求的工作量大小,单位:人月。
这部分需求需要在 M 个月内完成开发,进行人力安排后每个月人力时固定的。
目前要求每个月最多有 2 个需求开发,并且每个月需要完成的需求不能超过部门人力。
请帮助部门评估在满足需求开发进度的情况下,每个月需要的最小人力是多少?
输入为 M 和 requirements , M 表示需求开发时间要求, requirements 表示每个需求工作量大小, N 为 requirements 长度,
1≤N/2≤M≤N≤10000
1≤requirements[i]≤109
对于每一组测试数据,输出部门需要人力需求,行末无多余的空格
输入
3
3 5 3 4
输出
6
说明
输入数据两行,
第一行输入数据 3 表示开发时间要求,
第二行输入数据表示需求工作量大小,
输出数据一行,表示部门人力需求。
当选择人力为 6 时, 2 个需求量为 3 的工作可以在 1 个月里完成,其他 2 个工作各需要 1 个月完成。可以在 3 个月内完成所有需求。
当选择人力为 5 时, 4 个工作各需要 1 个月完成,一共需要 4 个月才能完成所有需求。
因此 6 是部门最小的人力需求。