#include <bits/stdc++.h>
using namespace std;

// Utility function to get maximum element in job[0..n-1]
int getMax(int arr[], int n) {
    int result = arr[0];
    for (int i = 1; i < n; i++)
        if (arr[i] > result)
            result = arr[i];
    return result;
}

// Returns true if it is possible to finish jobs[] within
// given time 'time' using K robots
bool isPossible(int time, int K, int job[], int n) {
    int cnt = 1;         // Number of robots currently used
    int curr_time = 0;   // Time assigned to the current robot

    for (int i = 0; i < n;) {
        // If assigning job[i] to the current robot exceeds 'time', 
        // increment the count of robots and reset curr_time
        if (curr_time + job[i] > time) {
            curr_time = 0;
            cnt++;
        } else {  // Else add time of job[i] to current robot's time
            curr_time += job[i];
            i++;
        }
    }

    // Returns true if count of robots used is <= K
    return (cnt <= K);
}

// Returns minimum time required to finish given array of jobs
// K --> number of robots
// T --> Time required by every robot to finish 1 unit of task
// job[] --> Array representing time each job takes
// n --> Number of jobs
int findMinTime(int K, int T, int job[], int n) {
    int end = 0, start = 0;
    for (int i = 0; i < n; ++i)
        end += job[i];  // Sum of all jobs is the upper limit for time

    int ans = end;  // Initialize answer with the upper limit
    int job_max = getMax(job, n);  // Find the job that takes maximum time

    // Binary search for minimum feasible time
    while (start <= end) {
        int mid = (start + end) / 2;

        // If it is possible to finish jobs in 'mid' time with K robots
        if (mid >= job_max && isPossible(mid, K, job, n)) {
            ans = min(ans, mid);  // Update answer
            end = mid - 1;        // Try for a smaller feasible time
        } else {
            start = mid + 1;      // Increase time if 'mid' is too small
        }
    }

    return (ans * T);  // Multiply by T to get the total time in units
}

// Driver program
int main() {
    int job[] = { 10, 20, 30, 40, 50 };  // Array of job times
    int n = sizeof(job) / sizeof(job[0]);  // Number of jobs
    int k = 2;  // Number of robots
    int T = 5;  // Time taken by each robot to move one unit of task

    cout << "Minimum time to complete all jobs: " << findMinTime(k, T, job, n) << " units" << endl;
    return 0;
}