Minimum Completion Time

You are given W workers and a list of tasks. Each task has an associated positive integer duration. The goal is to assign all tasks to the workers such that each worker processes tasks one after another, and the overall completion time is minimized.

Formally, let \(t_1, t_2, \dots, t_n\) be the durations of the tasks. If tasks are assigned to W workers, then the completion time is determined by the maximum total duration assigned to any worker. Note that the minimum possible time cannot be less than \(\max\{t_i\}\) and is optimized by assigning tasks in descending order to the worker with the current smallest load.

Your task is to compute the minimum total time required to complete all tasks.

inputFormat

The input is read from stdin and has the following format:

1. The first line contains an integer W representing the number of workers.
2. The second line contains an integer N representing the number of tasks.
3. The third line contains N space-separated integers, where each integer denotes the duration of a task.

outputFormat

Output to stdout a single integer representing the minimum completion time required to finish all tasks.

3
6
2 2 3 5 9 3

9