Question
Parallel Processors
There are N tasks waiting in line to be executed. The execution time for the ith task is Ai seconds. Ram has two processors to execute these N tasks. Both these processors work simultaneously. Each processor executes the assigned tasks one by one.Ram assigns a prefix of these tasks to the first processor and the remaining tasks to the second processor.
For example, if there are 3 tasks, Ram can do one of the following:
- Assign no task to the first processor. This means, the second processor will execute tasks 1,2 and 3.
- Assign task 1 to the first processor. This means, the second processor will execute tasks 2 and 3.
- Assign tasks 1 and 2 to the first processor. This means, the second processor will execute task 3.
- Assign tasks 1,2 and 3 to the first processor. Thus, second processor would execute no tasks.
Find the minimum time in which all the tasks can be executed.
Input
The first line of input contains an integer N denoting the length of the array.
The following line contains N space-separated integers A1, A2, ..... , An denoting the execution time of each task.
Constraints:
1 ≤ N ≤ 100
1 ≤ A[i] ≤ 10000
The following line contains N space-separated integers A1, A2, ..... , An denoting the execution time of each task.
Constraints:
1 ≤ N ≤ 100
1 ≤ A[i] ≤ 10000
Output
Return the minimum time in which all tasks can be executed.
Example
Sample Input:
3
4 2 3
Sample Output:
5
Explanation
Chef assigns task 1 to the first processor and tasks 2 and 3 to the second processor. The first processor takes 4 seconds to execute task 1.The second processor takes 2 + 3 = 5 seconds to execute tasks 2 and 3. Thus, at least 5 seconds are required to execute all tasks.
3
4 2 3
Sample Output:
5
Explanation
Chef assigns task 1 to the first processor and tasks 2 and 3 to the second processor. The first processor takes 4 seconds to execute task 1.The second processor takes 2 + 3 = 5 seconds to execute tasks 2 and 3. Thus, at least 5 seconds are required to execute all tasks.