Minimize Maximum Completion Time

You are given n assembly lines and m orders. Each order requires a certain amount of processing time. Your task is to assign the orders to these assembly lines such that the maximum completion time (i.e. the time taken by the busiest assembly line) is minimized.

Note: Orders are assigned one at a time under a greedy strategy: at each step, the next longest order is assigned to the assembly line that currently has the smallest load.

Mathematical formulation:

Let \(a_1, a_2, \dots, a_n\) denote the total processing time of orders assigned to each assembly line. We want to minimize \(\max\{a_1, a_2, \dots, a_n\}\) subject to the condition that every order must be assigned to one assembly line.

inputFormat

The first line of input contains two integers n and m (1 ≤ n ≤ m), representing the number of assembly lines and the number of orders, respectively.

The second line contains m space-separated integers, where each integer represents the processing time of an order.

outputFormat

Output a single integer – the minimized maximum completion time after assigning all orders optimally.

3 5
2 14 4 16 6

16