Minimum Task Completion Time

You are given \(n\) tasks with durations \(T_1, T_2, \ldots, T_n\) and \(k\) employees. Each employee can work on tasks sequentially. The tasks can be performed in any order, and the objective is to minimize the total time taken to complete all tasks.

The overall completion time is defined as:

\(T = \max_{1 \leq i \leq k} \left(\sum_{j \in S_i} T_j\right)\),

where \(S_i\) is the set of tasks assigned to the \(i\)-th employee. If there are more employees than tasks, the answer is the maximum task duration. Otherwise, tasks should be assigned greedily to the employee with the current minimum workload.

inputFormat

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

1. An integer \(n\) representing the number of tasks.
2. A line containing \(n\) space-separated integers representing the durations of the tasks.
3. An integer \(k\) representing the number of employees.

outputFormat

Output a single integer to standard output (stdout) which indicates the minimum time required to complete all tasks.

1
10
1

10