Ants Stealing Food

Near Prof. Pang's big house there is an ant colony with m ants living in a cave that has n holes. The ants go out through any hole to steal food from the big refrigerator. For any ant, leaving the cave (through any hole) takes 1 second and entering the cave takes 1 second. The distance between the i-th hole and the refrigerator is given by \(a_i\). Thus, after leaving the cave via the i-th hole an ant spends \(a_i\) seconds reaching the refrigerator, and after stealing food (which takes 0 time) it spends another \(a_i\) seconds going back to some (possibly different) hole to reenter the cave.

However, there is a catch: each hole can handle at most one ant per second. Moreover, in any given second a hole cannot be used simultaneously by an ant leaving and another ant entering. Each ant must complete exactly one round‐trip (i.e. leave exactly once and reenter exactly once).

The total time cost is defined as the length of the time interval during which at least one ant is outside the cave. Your task is to determine the minimum possible time such that all m ants can complete their mission without violating the hole‐capacity constraints.

Note: It is allowed that different ants choose different holes for leaving and entering. In an optimal schedule the ants will use the fastest hole for leaving (minimizing travel time) while the arriving operations are scheduled as early as possible subject to the capacity constraints. Formally, if we assume that we can schedule the departures as early as possible then the i-th ant (0-indexed) will have its departure completed at time \(\lfloor i/n\rfloor+1\). If the ant uses the fastest hole for leaving (with \(\min\{a_i\}\)) then its ready time for reentry is \(\lfloor i/n\rfloor+1+\min\{a_i\}\). On the other hand, for each hole \(j\), an arrival event using that hole takes 1 second and requires an additional \(a_j\) seconds after the arrival start, so an arrival scheduled at time t by hole \(j\) will finish at time \(t+1+a_j\); hence, in order to finish by time \(T\) we must have \(t\le T-1-a_j\). The problem is then to decide the minimum \(T\) such that one can match all ants’ arrival operations with an available arrival slot (from some hole) that occurs no earlier than the ant’s ready time.

Input and output descriptions follow.

inputFormat

The first line contains two integers \(m\) and \(n\) (the number of ants and the number of holes).
The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\) where \(a_i\) denotes the time (in seconds) required for an ant to travel between hole \(i\) and the refrigerator.

outputFormat

Output a single integer: the minimum total time cost (in seconds) such that all ants can complete their round‐trip without violating the hole capacity constraints.

sample

1 1
5

12