class Solution {
public:
    int ans=INT_MAX,sum[13]={0};
    int minimumTimeRequired(vector<int>& jobs, int k) {
        dfs(0,k,sum,jobs,0,0);
        return ans;
    }
    void dfs(int u,int k,int sum[],vector<int>jobs,int tepans,int use){
        if(tepans>=ans)return;
        if(u==jobs.size()){
            ans=min(ans,tepans);
            return;
        }
        if(use<k){
            sum[use]=jobs[u];
            dfs(u+1,k,sum,jobs,max(tepans,sum[use]),use+1);
            sum[use]=0;
        }
        for(int i=0;i<use;i++){
            sum[i]+=jobs[u];
            dfs(u+1,k,sum,jobs,max(tepans,sum[i]),use);
            sum[i]-=jobs[u];
        }
    }
};