Minimum Time to Complete Tasks

You are given N machines and M tasks. Each task requires a certain amount of processing time. Your goal is to determine the minimum time needed to complete all tasks if they are optimally assigned to the available machines. Each machine can work on one task at a time, and tasks assigned to the same machine are processed sequentially.

The problem can be modeled as scheduling tasks across multiple machines such that the maximum load (i.e. the time when the last task finishes) is minimized. A greedy strategy using a min-heap can be employed: assign each task (starting with the ones that require the most processing time) to the machine that becomes available the earliest.

Mathematically, if \(T_i\) denotes the processing time of the \(i^{th}\) task, and if the tasks are sorted in descending order, the goal is to minimize \(\max_{1 \leq j \leq N} (\sum_{i \in S_j} T_i)\) where \(S_j\) is the set of tasks assigned to machine \(j\).

inputFormat

The input is provided via standard input (stdin). The first line contains two integers (N) and (M) separated by a space, where (N) is the number of machines and (M) is the number of tasks. The second line contains (M) space-separated non-negative integers representing the processing time required for each task.

outputFormat

Output a single integer to standard output (stdout) — the minimum time required to complete all tasks.## sample

3 5
5 2 8 3 6

8