You want to schedule a list of jobs in d days. Jobs are dependent (i.e To work on the i-th job, you have to finish all the jobs j where 0 <= j < i).
You have to finish at least one task every day. The difficulty of a job schedule is the sum of difficulties of each day of the d days. The difficulty of a day is the maximum difficulty of a job done in that day.
Given an array of integers jobDifficulty and an integer d. The difficulty of the i-th job is jobDifficulty[i].
Return the minimum difficulty of a job schedule. If you cannot find a schedule for the jobs return -1.
 
Example 1:

Input: jobDifficulty = [6,5,4,3,2,1], d = 2
Output: 7
Explanation: First day you can finish the first 5 jobs, total difficulty = 6.
Second day you can finish the last job, total difficulty = 1.
The difficulty of the schedule = 6 + 1 = 7 

Example 2:
Input: jobDifficulty = [9,9,9], d = 4
Output: -1
Explanation: If you finish a job per day you will still have a free day. you cannot find a schedule for the given jobs.

Example 3:
Input: jobDifficulty = [1,1,1], d = 3
Output: 3
Explanation: The schedule is one job per day. total difficulty will be 3.

Example 4:
Input: jobDifficulty = [7,1,7,1,7,1], d = 3
Output: 15

Example 5:
Input: jobDifficulty = [11,111,22,222,33,333,44,444], d = 6
Output: 843

 
Constraints:

1 <= jobDifficulty.length <= 300
0 <= jobDifficulty[i] <= 1000
1 <= d <= 10

Difficulty: interview

Starter code:

class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        

Solutions:
class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        N = len(jobDifficulty)
        if N < d: 
            return -1
        
        dp = [jobDifficulty[0]]
        for j in jobDifficulty[1:]:
            dp.append(max(dp[-1], j))

        for i in range(1, d):
            
            dp_curr = [0] * N
            
            stack = []
            for j in range(i, N):
                dp_curr[j] = dp[j - 1] + jobDifficulty[j]
                
                while stack and jobDifficulty[stack[-1]] <= jobDifficulty[j]:
                    dp_curr[j] = min(dp_curr[j], dp_curr[stack[-1]] - jobDifficulty[stack[-1]] + jobDifficulty[j])
                    stack.pop()
                    
                if stack:
                    dp_curr[j] = min(dp_curr[j], dp_curr[stack[-1]]) 
                stack.append(j)
                
            dp = dp_curr
        return dp[-1]

class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        N = len(jobDifficulty)
        if N<d: return -1
        
        dp = [jobDifficulty[0]]
        for j in jobDifficulty[1:]:
            dp.append(max(dp[-1], j))

        for i in range(1, d):
            stack = []
            dp2 = [0]*N
            for j in range(i, N):
                dp2[j] = dp[j-1]+jobDifficulty[j]
                while stack and jobDifficulty[stack[-1]]<=jobDifficulty[j]:
                    dp2[j] = min(dp2[j], dp2[stack[-1]]-jobDifficulty[stack[-1]]+jobDifficulty[j])
                    # dp2[j] = min(dp2[j], dp[stack[-1]]+jobDifficulty[j])
                    stack.pop()
                    
                if stack:
                    dp2[j] = min(dp2[j], dp2[stack[-1]])
                    
                stack.append(j)
            dp = dp2
            # print(dp)
        return dp[-1]

class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        n = len(jobDifficulty)
        if d > n:
            return -1
        if d == n:
            return sum(jobDifficulty)
        
        dp = {}
        
        def moveOnce(d0, difficultyNow, i0):
            if d0 == d:
                return max(difficultyNow, max(jobDifficulty[i0:]))
            if n - i0-1 == d-d0:
                return max(jobDifficulty[i0], difficultyNow) + sum(jobDifficulty[i0+1:])
            
            if (d0, difficultyNow, i0) in dp:
                return dp[(d0, difficultyNow, i0)]
            
            subAns = min(moveOnce(d0, max(jobDifficulty[i0], difficultyNow), i0 + 1), max(jobDifficulty[i0], difficultyNow) + moveOnce(d0+1, jobDifficulty[i0+1], i0+1))
            
            dp[(d0, difficultyNow, i0)] = subAns
            
            return subAns
        
        return moveOnce(1, jobDifficulty[0], 0)

class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        N = len(jobDifficulty)
        if d > N: return -1
        memo = [[float('inf')] * (d + 1) for _ in range(N + 1)]
        memo[0][0] = 0
        for i in range(1, N + 1):
            for k in range(1, min(i, d) + 1):
                maxD = 0
                for j in range(i - 1, -1, -1):
                    maxD = max(maxD, jobDifficulty[j])
                    memo[i][k] = min(memo[i][k], memo[j][k - 1] + maxD)
        return memo[N][d]

class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        if d > len(jobDifficulty):
            return -1
        self.memo = {}
        self.mxs = []
        mx = 0
        for j in jobDifficulty:
            mx = max(mx, j)
            self.mxs.append(mx)
        return self.recurse(jobDifficulty, len(jobDifficulty) - 1, d)
        
    def recurse(self, jd, start, remain):
        # if start == 0:
        #     return jd[0]
        if remain == 1:
            # return max(jd[:start + 1])
            return self.mxs[start]
        
        if (start, remain) in self.memo:
            return self.memo[(start, remain)]
        
        mx = 0
        mn = float('inf')
        
        for j in range(start, 0, -1):
            curr = jd[j]
            mx = max(mx, curr)
            mn = min(mn, mx + self.recurse(jd, j - 1, remain - 1))
        self.memo[(start, remain)] = mn
        # print((start, remain), self.memo, mx, mn)
        return mn

class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        
        n = len(jobDifficulty)
        
        n, inf = len(jobDifficulty), float('inf')
        dp = [[inf] * n + [0] for i in range(d + 1)]
        for d in range(1, d + 1):
            for i in range(n - d + 1):
                maxd = 0
                for j in range(i, n - d + 1):
                    maxd = max(maxd, jobDifficulty[j])
                    dp[d][i] = min(dp[d][i], maxd + dp[d - 1][j + 1])
                
        return dp[d][0] if dp[d][0] < inf else -1

class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        n, inf = len(jobDifficulty), float('inf')
        
        dp = [[inf] * n + [0] for _ in range(d + 1)]
        
        for d in range(1, d + 1):
            for i in range(n - (d - 1)):
                maxd = 0
                for j in range(i, n - (d - 1)):
                    maxd = max(maxd, jobDifficulty[j])
                    dp[d][i] = min(dp[d][i], maxd + dp[d - 1][j + 1])
        return dp[d][0] if dp[d][0] < inf else -1

class Solution:
    def minDifficulty(self, A: List[int], d: int) -> int:
        n = len(A)
        
        if d>n: #more days than job
            return -1
        
        dp = [[math.inf]*(d+1) for _ in range(n)]
        #dp[i][j] store the ans for jobs i:n with j days remaining
        
        for i in range(n-1,-1,-1):
            for j in range(1,d+1):
                if n-i<j: #more days than jobs
                    continue
                rMax = -math.inf
                for k in range(i,n-j+1): #if we finish i:k+1 jobs today
                    rMax=max(rMax,A[k])
                    if j==1:
                        dp[i][j]=rMax
                    else:
                        dp[i][j] = min(dp[i][j],rMax+dp[k+1][j-1])
        return dp[0][d]


class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
     
        n, inf = len(jobDifficulty), float('inf')
        dp = [[inf] * n + [0] for i in range(d + 1)]
        for d in range(1, d + 1):
            for i in range(n - d + 1):
                maxd = 0
                for j in range(i, n - d + 1):
                    maxd = max(maxd, jobDifficulty[j])
                    dp[d][i] = min(dp[d][i], maxd + dp[d - 1][j + 1])
        return dp[d][0] if dp[d][0] < inf else -1
'''
Solution3: Bottom-up 1D DP
Time complexity O(nnd)
Space complexity O(n)'''

class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        n = len(jobDifficulty)
        if n < d:
            return -1
        # Init the above with padding
        # dp[k][i] means the min job difficulty when we want to schedule the first i tasks during k days
        dp = [[float('inf')] * (n + 1) for _ in range(d + 1)]
        dp[0][0] = 0
        #max_diff_right = jobDifficulty[n - 1]
        for k in range(1, d + 1):
            for i in range(1, n + 1):
                max_diff_right = 0
                for j in range(i - 1, k - 2, -1):
                    # Moving maximum to calculate max in O(1)
                    max_diff_right = max(max_diff_right, jobDifficulty[j])
                    dp[k][i] = min(dp[k][i], dp[k - 1][j] + max_diff_right)
        return dp[d][n]

# 11:19 - 
class Solution:
    def minDifficulty(self, difficulty: List[int], d: int) -> int:
        # dp[n, d] = dp[n - 1, d - i] + max(n - i, n) 
        if d > len(difficulty):
            return -1
        
        n = len(difficulty)
        dp = [[float('inf')] * (n + 1) for _ in range(d + 1)]
        dp[0][0] = 0
        
        # dp[i, j]: finish 'j' jobs in 'i' days
        for i in range(d):
            for j in range(n):
                local = float('-inf')
                for k in range(j, -1, -1):
                    if k < i:
                        break
                    local = max(local, difficulty[k])
                    dp[i + 1][j + 1] = min(dp[i + 1][j + 1], local + dp[i][k])
        
        return dp[d][n] if dp[d][n] != float('inf') else -1


class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        n = len(jobDifficulty)
        if d > n: return -1
        dp = [[float('inf') for _ in range(d+1)] for _ in range(n+1)]
        dp[0][0] = 0
        for i in range(1, n+1):  # number of days
            for k in range(1, d+1):   # number of jobs
                md = 0
                for j in range(i-1, k-2, -1):
                    md = max(md, jobDifficulty[j])
                    dp[i][k] = min(dp[i][k], dp[j][k-1]+md)
        return dp[-1][-1]


class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        if d > len(jobDifficulty): return -1
        if not jobDifficulty: return 0
        dp = [[float('inf') for _ in range(d+1)] for _ in range(len(jobDifficulty)+1)]
        dp[0][0] = 0                
        for i in range(1,len(jobDifficulty)+1):
            for j in range(1,d+1):
                tmp = 0
                # k-1 >= j-1
                for k in range(i,j-1,-1):
                    tmp = max(tmp,jobDifficulty[k-1])
                    dp[i][j] = min(dp[i][j], dp[k-1][j-1] + tmp)
        # print(dp)
        return dp[-1][-1] if dp[-1][-1] < float('inf') else -1

# 11:19 - 
class Solution:
    def minDifficulty(self, difficulty: List[int], d: int) -> int:
        # dp[n, d] = dp[n - 1, d - i] + max(n - i, n) 
        if d > len(difficulty):
            return -1
        
        n = len(difficulty)
        dp = [[float('inf')] * (n + 1) for _ in range(d + 1)]
        dp[0][0] = 0
        
        # dp[i, j]: finish 'j' jobs in 'i' days
        for i in range(d):
            for j in range(n):
                local = float('-inf')
                for k in range(j, -1, -1):
                    if k < i:
                        break
                    local = max(local, difficulty[k])
                    dp[i + 1][j + 1] = min(dp[i + 1][j + 1], local + dp[i][k])
        
        return dp[d][n]


class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        
        cumsum = [0]*len(jobDifficulty)
        cummax = [[0]*len(jobDifficulty) for _ in range(len(jobDifficulty))]
        
        for i in range(len(jobDifficulty)):
            cumsum[i] = cumsum[i-1] + jobDifficulty[i]
            for j in range(i, len(jobDifficulty)):
                cummax[i][j] = max(cummax[i][j-1], jobDifficulty[j])
                
        memo = {}
        
        @lru_cache        
        def DFS(s, d):
            if (s,d) in memo:
                return memo[s,d]
            if d > s:
                memo[s,d] = float('inf')
            elif d == s:
                memo[s,d] = cumsum[s-1]
            elif d == 1:
                memo[s,d] = cummax[0][s-1]
            else:
                memo[s,d] = min(cummax[i][s-1]+DFS(i,d-1) for i in range(1,s))
            return memo[s,d]
        
        res = DFS(len(jobDifficulty), d) 
        return res if res < float('inf') else -1
        


class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        jc = len(jobDifficulty)
        if d > jc: return -1
        dp = [[-1 for i in range(jc+1)] for i in range(d+1)]
        dp[1][1] = jobDifficulty[0]

        for i in range(2, jc+1):
            dp[1][i] = max(dp[1][i-1], jobDifficulty[i-1])
        
        for i in range(2, d+1):
            for j in range(i, jc+1):
                dp[i][j] = dp[i-1][j-1] + jobDifficulty[j-1]
                work = jobDifficulty[j-1]
                for k in range(j-2, i-2, -1):
                    work = max(jobDifficulty[k], work)
                    if dp[i-1][k] + work < dp[i][j]:
                        dp[i][j] = dp[i-1][k] + work
        return dp[d][jc]




class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        n = len(jobDifficulty)
        M = 1e6
        dp = [[M] * (d + 1) for i in range(n + 1)]
        dp[n][0] = 0
        dp[n - 1][1] = jobDifficulty[n - 1]
        for i in range(n - 2, -1, -1):
            for j in range(1, d + 1):
                m = -1
                for k in range(i, n):
                    m = max(m, jobDifficulty[k])
                    dp[i][j] = min(dp[i][j], m + dp[k + 1][j - 1])
        return dp[0][d] if dp[0][d] < M else -1


class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        
        n = len(jobDifficulty)
        dp = [[float('inf')] * n +[0] for _ in range(d + 1)]
        
        for d in range(1, d+1):
            for i in range(n - d + 1):
                maxd = 0
                for j in range(i, n-d+1):
                    maxd = max(maxd, jobDifficulty[j])
                    dp[d][i] = min(dp[d][i], maxd+dp[d-1][j+1])
        
        return dp[d][0] if dp[d][0] < float('inf') else -1

class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        
        cumsum = [0]*len(jobDifficulty)
        cummax = [[0]*len(jobDifficulty) for _ in range(len(jobDifficulty))]
        
        for i in range(len(jobDifficulty)):
            cumsum[i] = cumsum[i-1] + jobDifficulty[i]
            for j in range(i, len(jobDifficulty)):
                cummax[i][j] = max(cummax[i][j-1], jobDifficulty[j])
                
        memo = {}
                
        
        
        @lru_cache()
        def DFS(s, d):
            if (s,d) in memo:
                return memo[s,d]
            if d > s:
                memo[s,d] = float('inf')
            elif d == s:
                memo[s,d] = cumsum[s-1]
            elif d == 1:
                memo[s,d] = cummax[0][s-1]
            else:
                memo[s,d] = min(cummax[i][s-1]+DFS(i,d-1) for i in range(1,s))
            return memo[s,d]
        
        res = DFS(len(jobDifficulty), d) 
        return res if res < float('inf') else -1
        


class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        n = len(jobDifficulty)
        if n < d:
            return -1
        # dp[i][k] means the min job difficulty when we want to schedule the first i tasks during k days
        dp = [ [float('inf')] * (d + 1) for _ in range(n + 1)]
        dp[0][0] = 0
        # Init the above with padding
        for i in range(1, n + 1):
            for k in range(1, d + 1):
                max_difficulty = 0
                j = i - 1
                while j >= k - 1:
                    #print(max_difficulty)
                    max_difficulty = max(max_difficulty, jobDifficulty[j])
                    #print(dp)
                    dp[i][k] = min(dp[i][k], dp[j][k - 1] + max_difficulty)
                    j -= 1
        print(dp)
        return dp[n][d]

class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        
        @lru_cache(maxsize=None)
        def job_max(i, j):
            return max(jobDifficulty[i:j])
        
        @lru_cache(maxsize=None)
        def job_sum(i, j):
            return sum(jobDifficulty[i:j])
        
        
        
        @lru_cache(maxsize=None)
        def DFS(s, d):
            if d > s:
                return float('inf')
            if d == s:
                return job_sum(0, s)
            if d == 1:
                return job_max(0, s)
            
            return min(job_max(i, s)+DFS(i,d-1) for i in range(1,s))
        
        res = DFS(len(jobDifficulty), d) 
        return res if res < float('inf') else -1
        


class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        N = len(jobDifficulty)
        if N < d:
            return -1

        dp = [[-1] * (d + 1) for _ in range(N)]
        
        def dfs(idx, d):
            if d == 0:
                if idx == N:
                    return 0
                else:
                    return math.inf
            
            if idx == N:
                return math.inf
            
            if dp[idx][d] != -1:
                return dp[idx][d]
            
            res = math.inf
            day_max = 0
            
            for j in range(idx, N):
                day_max = max(day_max, jobDifficulty[j])
                res = min(res, day_max + dfs(j + 1, d - 1))


            dp[idx][d] = res
            return res
        
        return dfs(0, d)

class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        n = len(jobDifficulty)
        if n < d:
            return -1

        self.memo = {}
        def check(left_days, i):
            ky = (left_days, i)
            if ky in self.memo:
                return self.memo[ky]

            m = n - left_days
            diff = jobDifficulty[i]
            mn = float('inf')
            while i < m:
                diff = max(diff, jobDifficulty[i])
                if left_days > 0:
                    mn = min(mn, diff + check(left_days - 1, i+1))
                else:
                    mn = diff
                i += 1
            self.memo[ky] = mn
            return mn

        return check(d-1,0)
        


class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        
        cumsum = [0]*len(jobDifficulty)
        cummax = [[0]*len(jobDifficulty) for _ in range(len(jobDifficulty))]
        
        for i in range(len(jobDifficulty)):
            cumsum[i] = cumsum[i-1] + jobDifficulty[i]
            for j in range(i, len(jobDifficulty)):
                cummax[i][j] = max(cummax[i][j-1], jobDifficulty[j])
                
        
        @lru_cache(maxsize=None)       
        def DFS(s, d):
            if d > s:
                return float('inf')
            elif d == s:
                return cumsum[s-1]
            elif d == 1:
                return cummax[0][s-1]
            else:
                return min(cummax[i][s-1]+DFS(i,d-1) for i in range(1,s))
        
        res = DFS(len(jobDifficulty), d) 
        return res if res < float('inf') else -1
        


class Solution:
    def minDifficulty(self, A: List[int], d: int) -> int:
        
        
        
        # my solution ... 
        #  time: O()
        # space: O()
        
        seen = {}
        def func(sidx, d):  # 返回在 d 天内完成 A[sidx:] 的结果
            if n-sidx < d:
                return float('inf')
            if d == 0:
                return float('inf') if sidx < n else 0
            if n-sidx == d:
                return sum(A[sidx:])
            if (sidx,d) not in seen:
                res = float('inf')
                cmax = A[sidx]
                for eidx in range(sidx, n):
                    if cmax < A[eidx]:
                        cmax = A[eidx]
                    res = min(res, cmax + func(eidx+1, d-1))
                seen[sidx,d] = res
            return seen[sidx,d]
        n = len(A)
        if n  < d: return -1
        if n == d: return sum(A)
        return func(0, d)
        
        


class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        inf = sum(jobDifficulty)
        mem = {}
        def dfs(i, d):
            if (i, d) in mem:
                return mem[(i, d)]
            if d == 0:
                if i == len(jobDifficulty):
                    mem[(i, d)] = (True, 0)
                    return True, 0
                else:
                    mem[(i, d)] = (False, None)
                    return False, inf
            else:
                success = False
                min_diff = inf
                cur_day_diff = 0
                for end in range(i, len(jobDifficulty)-d+1):
                    cur_day_diff = max(cur_day_diff, jobDifficulty[end])
                    next_success, next_diff = dfs(end+1, d-1)
                    if next_success:
                        success = True
                        min_diff = min(min_diff, cur_day_diff+next_diff)
                mem[(i, d)] = (success, min_diff)
                return success, min_diff
        success, min_diff = dfs(0, d)
        if success:
            return min_diff
        else:
            return -1


class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        '''
        max_d(i,i+k-1) = 
        
        dp(i, d_left) = 
        if d_left == 0: 
            return float('inf')
        if i == len(jobDifficulty)-1:
            if d_left > 1:
                return float('inf')
            else:
                return jobDifficulty[i]
        
        for k in range(1, len(jobDifficulty)-i):
            res = min(res, dp(i+k, d_left-1) + max_d(i,i+k-1))
        
        
        jobDifficulty = [6,5,4,3,2,1], d = 2
        '''
        max_d = [[-1 for _ in range(len(jobDifficulty))] for _ in range(len(jobDifficulty))]
        for i in range(len(jobDifficulty)):
            max_d[i][i] = jobDifficulty[i]
            for j in range(i+1, len(jobDifficulty)):
                max_d[i][j] = max(jobDifficulty[j], max_d[i][j-1])
        def dp(i, d_left):
            if d_left == 0: 
                return float('inf')
            if d_left == 1: return max_d[i][-1]
            if i == len(jobDifficulty)-1:
                if d_left > 1:
                    return float('inf')
                else:
                    return jobDifficulty[i]
            if (i, d_left) in memo.keys(): return memo[(i, d_left)]
            res = float('inf')
            for k in range(1, len(jobDifficulty)-i):
                res = min(res, dp(i+k, d_left-1) + max_d[i][i+k-1])
            
            memo[(i, d_left)] = res
            return res
        memo = {}
        
        ans = dp(0, d)
        # print(max_d)
        # print(memo)
        return ans if ans != float('inf') else -1

class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        n = len(jobDifficulty)
        if d > n:
            return -1
        dp = [[-1 for _ in range(d+1)] for _ in range(n)]
        return self.helper(jobDifficulty, n, 0, d, dp)
    
    def helper(self, jobDifficulty, n, idx, d, dp):
        if idx == n and d == 0:
            return 0
        if idx == n or d == 0:
            return float('inf')
        if dp[idx][d] != -1:
            return dp[idx][d]
        minDiff = float('inf')
        currMax = jobDifficulty[idx]
        for j in range(idx, n):
            currMax = max(currMax, jobDifficulty[j])
            temp = self.helper(jobDifficulty, n, j+1, d-1, dp)
            minDiff = min(minDiff, temp + currMax)
        dp[idx][d] = minDiff
        return minDiff


class Solution:                              
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        n = len(jobDifficulty)
        if n < d:
            return -1
        dp = [[float('inf') for _ in range(d+1)] for _ in range(n+1)]
        dp[0][0] = 0
        for i in range(1,n+1):
            for k in range(1,d+1):
                tmp_max = 0
                for j in range(i-1,k-2,-1):
                    tmp_max = max(tmp_max,jobDifficulty[j])
                    dp[i][k] = min(dp[i][k],dp[j][k-1]+tmp_max)
        return dp[-1][-1]
        
        
    def minDifficulty_TLE(self, jobDifficulty: List[int], d: int) -> int:
        n = len(jobDifficulty)
        if n < d:
            return -1
        dp = [[0 for _ in range(n)] for _ in range(n)]
        for i in range(n):
            for j in range(i,n):
                dp[i][j] = max(jobDifficulty[i:j+1])
        # print(dp)
        res = [float('inf')]
        def search(i,j,val): # i- cut, j - idx
            if i == d:
                res[0] = min(res[0],val+(0 if j >= n else dp[j][-1]))
                return
            for k in range(j,n):
                search(i+1,k+1,val+dp[j][k])
        search(0,0,0)
        return res[0]


class Solution:
    def minDifficulty(self, arr: List[int], d: int) -> int:
        if len(arr)<d:
            return -1
        memo = [[None]*(d+1) for _ in range(len(arr)+1)]
        def dp(jobs, days):
            if days <0:
                return -1
            if memo[jobs][days] is not None:
                return memo[jobs][days]
            if jobs < days:
                memo[jobs][days] = -1
                return -1
            if d == 1:
                memo[jobs][days] = max(arr[:jobs])
                return max(arr[:jobs])
            if jobs==days:
                memo[jobs][days] = sum(arr[:jobs])
                return sum(arr[:jobs])
            res = -1
            rm = arr[jobs-1]
            for i in range(1, jobs+1):
                rm = max(rm, arr[jobs-i])
                temp = dp(jobs-i, days-1)
                if temp!=-1:
                    if res == -1:
                        res = temp + rm
                    else:
                        res = min(res, temp+rm)
            memo[jobs][days] = res
            return res
        return dp(len(arr), d)
    
#     import functools
    
#     def minDifficulty1(self, A, d):
#         calls = 0
#         n = len(A)
#         if n < d: return -1

#         @functools.lru_cache(None)
#         def dfs(i, d):
#             nonlocal calls
#             calls += 1
#             if d == 1:
#                 return max(A[i:])
#             res, maxd = float('inf'), 0
#             for j in range(i, n - d + 1):
#                 maxd = max(maxd, A[j])
#                 res = min(res, maxd + dfs(j + 1, d - 1))
#             return res
#         res = dfs(0, d)
#         print(calls)
#         return res


class Solution:
    def minDifficulty(self, A: List[int], d: int) -> int:
        
        
        
        # my solution ... 1272 ms ... 48 % ... 14.8 MB ... 39 %
        #  time: O(2^n)
        # space: O(n*d)
        
        seen = {}
        def func(sidx, d):  # 返回在 d 天内完成 A[sidx:] 的结果
            if sidx == n or d == 0:
                return 0 if (sidx == n and d == 0) else float('inf')
            if n-sidx < d:
                return float('inf')
            if n-sidx == d:
                return endsum[sidx]
            
            if (sidx, d) not in seen:
                res = float('inf')
                curmax = A[sidx]
                for eidx in range(sidx, n):
                    if curmax < A[eidx]:
                        curmax = A[eidx]
                    res = min(res, curmax + func(eidx+1, d-1))
                seen[sidx, d] = res
            return seen[sidx, d]
        
        n = len(A)
        if n  < d: return -1
        if n == d: return sum(A)
        endsum = [A[-1]] * n
        for j in range(n-2, -1, -1):
            endsum[j] = A[j] + endsum[j+1]
        return func(0, d)
        
        


import functools
class Solution:

    def minDifficulty(self, A, d):
        n = len(A)
        if n < d: return -1

        @functools.lru_cache(None)
        def dfs(i, d):
            if d == 1:
                return max(A[i:])
            res, maxd = float('inf'), 0
            for j in range(i, n - d + 1):
                maxd = max(maxd, A[j])
                res = min(res, maxd + dfs(j + 1, d - 1))
            return res
        return dfs(0, d)

# class Solution:
#     def minDifficulty(self, A, d):
#         \"\"\"
#         :type jobDifficulty: List[int]
#         :type d: int
#         :rtype: int
#         \"\"\"
#         self.n = len(A)
#         self.A = A
#         if self.n < d: 
#             return -1
        
#         return self.dfs(0, d)
    
#     @functools.lru_cache(None)
#     def dfs(self, i, d):
#         if d == 1:
#             return max(self.A[i:])
#         res, maxd = float('inf'), 0
#         for j in range(i, self.n - d + 1):
#             maxd = max(maxd, self.A[j])
#             res = min(res, maxd + self.dfs(j + 1, d - 1))
#         return res



class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        if len(jobDifficulty) < d:
            return -1
        elif len(jobDifficulty) == d:
            return sum(jobDifficulty)
        
        matrix = [[0] * len(jobDifficulty) for i in range(len(jobDifficulty))]
        
        for i in range(len(jobDifficulty)):
            for j in range(i,len(jobDifficulty)):
                if i == j:
                    matrix[i][j] = jobDifficulty[j]
                else:
                    matrix[i][j] = max(matrix[i][j-1], jobDifficulty[j])
        
        dp = [[float('inf')] * len(jobDifficulty) for i in range(d)]
        
        for i in range(d):
            for j in range(i,len(jobDifficulty)):
                if i == 0:
                    dp[i][j] = matrix[i][j]
                else:
                    if j > 0:
                        dp[i][j] = min([matrix[j-k][j]+dp[i-1][j-k-1] for k in range(0,j)])
   
        return dp[-1][-1]

# 11:19 - 
class Solution:
    def minDifficulty(self, difficulty: List[int], d: int) -> int:
        # dp[n, d] = dp[n - 1, d - i] + max(n - i, n) 
        if d > len(difficulty):
            return -1
        
        n = len(difficulty)
        dp = [[float('inf')] * (n + 1) for _ in range(2)]
        dp[1][0] = 0
        
        # dp[i, j]: finish 'j' jobs in 'i' days
        for i in range(d):
            for j in range(n):
                dp[i & 1][j + 1] = float('inf')
                local = float('-inf')
                for k in range(j, -1, -1):
                    if k < i:
                        break
                    local = max(local, difficulty[k])
                    dp[i & 1][j + 1] = min(dp[i & 1][j + 1], local + dp[(i + 1) & 1][k])
        
        return dp[(d - 1) & 1][-1]


class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        jD=jobDifficulty
        day=d
        self.memo = {}
        def dp(i,day):
            if (i,day) not in self.memo:
                if i < day: self.memo[(i,day)] = float('inf')
                elif day == 1: self.memo[(i,day)] = max(jD[:i])
                elif i == day: self.memo[(i,day)] = sum(jD[:i])
                else:
                    tmp = jD[i-1]
                    self.memo[(i,day)] = dp(i-1,day-1) + tmp
                    for j in range(i-1,day-3,-1):
                        tmp = max(jD[j-1],tmp)
                        self.memo[(i,day)] = min(self.memo[(i,day)],dp(j,day-1) + tmp)
            return self.memo[(i,day)]
        ans = dp(len(jD),d)
        return ans if ans!= float('inf') else -1


class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        n, inf = len(jobDifficulty), float('inf')
        
        dp = [[inf] * n + [0] for _ in range(d + 1)]
        
        for d in range(1, d + 1):
            for i in range(n - (d - 1)):
                maxd = 0
                for j in range(i, n - (d - 1)):
                    maxd = max(maxd, jobDifficulty[j])
                    dp[d][i] = min(dp[d][i], maxd + dp[d - 1][j + 1])
        print(dp)
        return dp[d][0] if dp[d][0] < inf else -1

class Solution:
    def minDifficulty(self, J: List[int], d: int) -> int:
        if len(J) < d: return -1
        
        dp = {} # (index of day, index of the last finished job)
        for i,job in enumerate(J):
            # the base case, all jobs need to be finish in one day
            dp[0, i] = max(dp.get((0, i-1), 0), job)
            
        for i in range(1, d):
            for j in range(i, len(J)):
                mx = J[j]
                for k in range(j, i-1, -1):
                    mx = max(mx, J[k])
                    dp[i, j] = min(dp.get((i, j), math.inf), mx + dp[i-1, k-1])
                
        return dp[d-1, len(J)-1]


class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        n = len(jobDifficulty)
        dp = {}
        def helper(i, d):
            if d == 0 and i == n:
                return 0
            if i >= n or d <= 0 or i + d > n:
                return float('inf')
            
            if (i, d) in dp:
                return dp[(i, d)]
            
            cur_max = 0
            cur_res = float('inf')
            for j in range(i, n - d + 1):
                cur_max = max(cur_max, jobDifficulty[j])
                cur_res = min(cur_res, cur_max + helper(j + 1, d - 1))
            
            dp[(i, d)] = cur_res
            return cur_res
        
        res = helper(0, d)
        return res if res != float('inf') else -1


class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        jD=jobDifficulty
        day=d
        self.memo = {}
        def dp(i,day):
            if (i,day) not in self.memo:
                if i < day: self.memo[(i,day)] = float('inf')
                elif day == 1: self.memo[(i,day)] = max(jD[:i])
                elif i == day: self.memo[(i,day)] = sum(jD[:i])
                else:
                    tmp = jD[i-1]
                    self.memo[(i,day)] = dp(i-1,day-1) + tmp
                    for j in range(i-1,day-3,-1):
                        tmp = max(jD[j-1],tmp)
                        self.memo[(i,day)] = min(self.memo[(i,day)],dp(j,day-1) + tmp)
            return self.memo[(i,day)]
        return dp(len(jD),d) if dp(len(jD),d) != float('inf') else -1


class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        if d > len(jobDifficulty):
            return -1
        self.memo = {}
        return self.recurse(jobDifficulty, len(jobDifficulty) - 1, d)
        
    def recurse(self, jd, start, remain):
        # if start == 0:
        #     return jd[0]
        if remain == 1:
            return max(jd[:start + 1])
        
        if (start, remain) in self.memo:
            return self.memo[(start, remain)]
        
        mx = 0
        mn = float('inf')
        total = float('inf')
        for j in range(start, 0, -1):
            curr = jd[j]
            mx = max(mx, curr)
            mn = min(mn, mx + self.recurse(jd, j - 1, remain - 1))
        self.memo[(start, remain)] = mn
        # print((start, remain), self.memo, mx, mn)
        return mn

class Solution:
    def minDifficulty(self, jD: List[int], d: int) -> int:
        self.memo = {}
        def dp(i,day):
            if (i,day) not in self.memo:
                if i < day: self.memo[(i,day)] = float('inf')
                elif day == 1: self.memo[(i,day)] = max(jD[:i])
                elif i == day: self.memo[(i,day)] = sum(jD[:i])
                else:
                    tmp = jD[i-1]
                    self.memo[(i,day)] = dp(i-1,day-1) + tmp
                    for j in range(i-1,day-3,-1):
                        tmp = max(jD[j-1],tmp)
                        self.memo[(i,day)] = min(self.memo[(i,day)],dp(j,day-1) + tmp)
            return self.memo[(i,day)]
        return dp(len(jD),d) if dp(len(jD),d) != float('inf') else -1



class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        if d > len(jobDifficulty):
            return -1
        dp = [[-1 for _ in range(d+1)] for _ in range(len(jobDifficulty))]
        return self.helper(jobDifficulty, 0, d, dp)
    
    def helper(self, jobDifficulty, idx, d, dp):
        if idx == len(jobDifficulty) and d == 0:
            return 0
        if idx == len(jobDifficulty) or d == 0:
            return float('inf')
        if dp[idx][d] != -1:
            return dp[idx][d]
        minDiff = float('inf')
        currMax = jobDifficulty[idx]
        for j in range(idx, len(jobDifficulty)):
            currMax = max(currMax, jobDifficulty[j])
            temp = self.helper(jobDifficulty, j+1, d-1, dp)
            minDiff = min(minDiff, temp + currMax)
        dp[idx][d] = minDiff
        return minDiff


class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        n = len(jobDifficulty)
        res = [0]
        dp = {}
        def helper(i, d):
            if d == 0 and i == n:
                return 0
            if i >= n or d <= 0 or i + d > n:
                return float('inf')
            
            if (i, d) in dp:
                return dp[(i, d)]
            
            cur_max = 0
            cur_res = float('inf')
            for j in range(i, n):
                cur_max = max(cur_max, jobDifficulty[j])
                cur_res = min(cur_res, cur_max + helper(j + 1, d - 1))
            
            dp[(i, d)] = cur_res
            return cur_res
        
        res = helper(0, d)
        return res if res != float('inf') else -1


class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        n = len(jobDifficulty)
        if d > n:
            return -1
        dp = [[-1 for _ in range(d+1)] for _ in range(n)]
        return self.helper(jobDifficulty, n, 0, d, dp)
    
    def helper(self, jobDifficulty, n, idx, d, dp):
        if idx == n and d == 0:
            return 0
        if idx == n or d == 0:
            return float('inf')
        if dp[idx][d] != -1:
            return dp[idx][d]
        minDiff = float('inf')
        currMax = jobDifficulty[idx]
        for j in range(idx, n):
            currMax = max(currMax, jobDifficulty[j])
            temp = self.helper(jobDifficulty, n, j+1, d-1, dp)
            if temp != float('inf'):
                minDiff = min(minDiff, temp + currMax)
        dp[idx][d] = minDiff
        return minDiff


class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        if d > len(jobDifficulty):
            return -1
        self.memo = {}
        return self.recurse(jobDifficulty, len(jobDifficulty) - 1, d)
        
    def recurse(self, jd, start, remain):
        # if start == 0:
        #     return jd[0]
        if remain == 1:
            return max(jd[:start + 1])
        
        if (start, remain) in self.memo:
            return self.memo[(start, remain)]
        
        mx = 0
        mn = float('inf')
        
        for j in range(start, 0, -1):
            curr = jd[j]
            mx = max(mx, curr)
            mn = min(mn, mx + self.recurse(jd, j - 1, remain - 1))
        self.memo[(start, remain)] = mn
        # print((start, remain), self.memo, mx, mn)
        return mn

class Solution:
    def minDifficulty(self, jD: List[int], d: int) -> int:
        self.memo = {}
        def dp(i,day):
            if (i,day) not in self.memo:
                if i < day: self.memo[(i,day)] = float('inf')
                elif day == 1: self.memo[(i,day)] = max(jD[:i])
                elif i == day: self.memo[(i,day)] = sum(jD[:i])
                else:
                    tmp = jD[i-1]
                    self.memo[(i,day)] = dp(i-1,day-1) + tmp
                    for j in range(i-1,day-3,-1):
                        tmp = max(jD[j-1],tmp)
                        self.memo[(i,day)] = min(self.memo[(i,day)],dp(j,day-1) + tmp)
            return self.memo[(i,day)]
        return dp(len(jD),d) if dp(len(jD),d) != float('inf') else -1

class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        n = len(jobDifficulty)
        if d > n:
            return -1
        
        max_table = [[0]*n for _ in range(n)]
        for i in range(n):
            max_table[i][i] = jobDifficulty[i]
            for j in range(i+1,n):
                max_table[i][j] = max(max_table[i][j-1], jobDifficulty[j])
        
        memo = [[0]*n for _ in range(d)]
        
        for j in range(n):
            memo[0][j] = max_table[0][j]
        
        for i in range(1, d):
            #memo[i][i] = max_table[i][i]
            for j in range(i,n):
                memo[i][j] = min(memo[i-1][t] + max_table[t+1][j] for t in range(i-1,j))
        
        return memo[-1][-1]
        


class Solution:
    def dfs(self, jobDifficulty, start_day, d, memo):
        if d == 1:
            return max(jobDifficulty[start_day:])

        if (start_day, d) in memo:
            return memo[(start_day, d)]
        
        min_diff = float('inf')
        cur_max_diff = 0

        for i in range(start_day, len(jobDifficulty) - d + 1):
            cur_max_diff = max(cur_max_diff, jobDifficulty[i])
            min_diff = min(min_diff, cur_max_diff + self.dfs(jobDifficulty, i + 1, d - 1, memo))
        
        memo[(start_day, d)] = min_diff
        return min_diff

    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        if len(jobDifficulty) < d:
            return -1

        memo = collections.defaultdict(int)
        return self.dfs(jobDifficulty, 0, d, memo)


class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        memo = {}
        def min_difficulty(i, days_left):
            if (i, days_left) in memo:
                return memo[i, days_left]
            
            if i == len(jobDifficulty):
                if days_left == 0:
                    return 0
                else:
                    return math.inf
            if days_left == 1:
                return max(jobDifficulty[i:])
            
            day_cost = 0
            min_so_far = math.inf
            for j in range(i, len(jobDifficulty)):
                day_cost = max(day_cost, jobDifficulty[j])
                remaining_cost = min_difficulty(j+1, days_left - 1)
                min_so_far = min(min_so_far, day_cost + remaining_cost)
                
            memo[i, days_left] = min_so_far
            return min_so_far
        
        answer = min_difficulty(0, d)
        if answer == math.inf:
            return -1
        else:
            return answer


class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        import functools
        n = len(jobDifficulty)
        if n < d:
            return -1
        @functools.lru_cache(None)
        def dfs(i, d):
            if d == 1:
                return max(jobDifficulty[i:])
            res, maxd = float('inf'), 0
            for j in range(i, n-d+1):
                maxd = max(maxd, jobDifficulty[j])
                res = min(res, maxd + dfs(j+1, d-1))
            return res
        return dfs(0, d)

class Solution:
    # def minDifficulty(self, A: List[int], d: int) -> int:
    #     if len(A) < d:
    #         return -1
    #     dp = {}
    #     def diff(i,d,maxVal):
    #         if i == len(A):
    #             return 10**9
    #         if d == 1:
    #             return max(maxVal, max(A[i:]))
    #         if (i,d,maxVal) in dp:
    #             return dp[(i,d,maxVal)]
    #         maxVal = max(maxVal,A[i])
    #         dp[(i,d,maxVal)] =  min(diff(i+1,d, maxVal), maxVal+diff(i+1,d-1,0))
    #         return dp[(i,d,maxVal)]
    #     return diff(0,d,0)
    
    def minDifficulty(self, A: List[int], d: int) -> int:
        if len(A) < d:
            return -1
        dp = {}
        def dfs(i,d):
            if d == 1:
                return max(A[i:])
            if (i,d) in dp:
                return dp[(i,d)]
            minVal = float('inf')
            maxNow = 0
            for j in range(i,len(A)-d+1):
                maxNow = max(maxNow, A[j])
                minVal = min(minVal,dfs(j+1,d-1)+maxNow)
            dp[(i,d)] =  minVal
            return dp[(i,d)]
        return dfs(0,d)
    


class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        if d > len(jobDifficulty):
            return -1
        memo = {}
        def dfs(idx, d):
            if (idx,d) in memo:
                return memo[(idx,d)]
            
            if d == 1:
                return max(jobDifficulty[idx:])
            
            day_difficulty, total_difficulty = -float('inf'), float('inf')
            for i in range(idx, len(jobDifficulty) -d + 1):
                day_difficulty = max(day_difficulty, jobDifficulty[i])
                total_difficulty = min(total_difficulty, day_difficulty + dfs(i + 1, d - 1))
            memo[(idx,d)] = total_difficulty
            return memo[(idx,d)]
        
        return dfs(0, d)

class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        # dp
        # time: O(n^2 * d)
        # space: O(nd)
        
        # dp[i][j]=min(dp[k][j-1]+max(jobD[k:i]))
        
        
        if len(jobDifficulty)<d:
            return -1
        
        n=len(jobDifficulty)
        dp=[[float('inf')]*(d+1) for _ in range(n+1)]
        
        maxVal={}
        
        for i in range(1, n+1):
            for j in range(i+1, n+1):
                maxVal[(i, j)]=max(jobDifficulty[i:j])
                
        for i in range(1, n+1):
            dp[i][1]=max(jobDifficulty[:i])
            
        for i in range(1, n+1):
            for j in range(2, d+1):
                if i>=j:
                    for k in range(j-1, i):
                        dp[i][j]=min(dp[i][j], dp[k][j-1]+maxVal[(k, i)])

        
        return dp[n][d]


class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        if d > len(jobDifficulty):
            return -1
        
        N = len(jobDifficulty)
        dp = {}
        
        def f(i, n):
            if N - i == n:
                return sum(jobDifficulty[i:])
            
            if n == 1:
                return max(jobDifficulty[i:])
            
            if (i, n) in dp:
                return dp[(i, n)]
            
            res = None
            curr = 0
            
            for j in range(i, N-n+1):
                curr = max(curr, jobDifficulty[j])
                if not res:
                    res = curr + f(j+1, n-1)
                else:
                    res = min(res, curr + f(j+1, n-1))
            
            dp[(i, n)] = res
            return res
            
        return f(0, d)

import functools
class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        n = len(jobDifficulty)
        if n < d:
            return -1
        @functools.lru_cache(None)
        def dfs(i, d):
            if d == 1:
                return max(jobDifficulty[i:])
            res, maxd = float('inf'), 0
            for j in range(i, n - d + 1):
                maxd = max(maxd, jobDifficulty[j])
                res = min(res, maxd + dfs(j+1, d-1))
            return res
        return dfs(0, d)

class Solution:
    def minDifficulty(self, jobDifficulty: List[int], D: int) -> int:
        n = len(jobDifficulty)
        dp = [[float('inf')]*n+[0] for _ in range(D+1)]
        for d in range(1,D+1):
            for i in range(n-d+1):
                maxd = 0
                for j in range(i,n-d+1):
                    maxd = max(maxd, jobDifficulty[j])
                    dp[d][i] = min(dp[d][i],maxd+dp[d-1][j+1])
        return dp[D][0] if dp[D][0]<float('inf') else -1

class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        cache = {}
        
        self.helper(jobDifficulty, 0, d, cache)
        
        result = cache.get((0, d))
        return -1 if result is None or result == float('inf') else result
    
        
    def helper(self, jobDifficulty, i, d, cache):
        if (i, d) in cache:
            return cache[(i, d)]
        if i == len(jobDifficulty) and d == 0:
            return 0
        if d <= 0 or len(jobDifficulty) - i < d:
            return float('inf')
        
        maxVal = -1
        cache[(i, d)] = float('inf')
        for j in range(i, len(jobDifficulty)): 
            maxVal = max(maxVal, jobDifficulty[j])
            result = maxVal + self.helper(jobDifficulty, j+1, d - 1, cache)
            cache[(i, d)] = min(cache[(i, d)], result)
        
        return cache[(i, d)]

class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        
        seen = {}

        def minDifficultyRestOfJobs(start, days_left):
            
            if (start, days_left) in seen: return seen[(start, days_left)]

            if len(jobDifficulty[start:]) < days_left:
                return float('inf')

            if days_left == 1:
                return max(jobDifficulty[start:])
            
            max_difficulty_today, total_difficulty = float('-inf'), float('inf')
            for job_idx in range(start, len(jobDifficulty)):
                max_difficulty_today = max(max_difficulty_today, jobDifficulty[job_idx])
                total_difficulty = min(total_difficulty, max_difficulty_today + minDifficultyRestOfJobs(job_idx+1, days_left-1))
            
            seen[(start, days_left)] = total_difficulty

            return total_difficulty

        res = minDifficultyRestOfJobs(0, d)
        return -1 if res == float('inf') else res   

class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        size = len(jobDifficulty)
        memoi = [jobDifficulty[0]] * size
        for i in range(1, size):
            memoi[i] = max(memoi[i-1], jobDifficulty[i])
        maxes = {(0, i): memoi[i-1] for i in range(1, size + 1)}
        def findMax(s, e):
            if (s, e) in maxes: return maxes[s, e]
            maxes[s, e] = max(jobDifficulty[s:e])
            return maxes[s, e]
        for cut in range(1, d):
            newMemoi = [float('inf')] * size
            for end in range(cut, size):
                for split in range(cut - 1, end):
                    newMemoi[end] = min(
                        newMemoi[end],
                        memoi[split] + findMax(split+1, end+1)
                    )
            memoi = newMemoi
        return memoi[-1] if memoi[-1] != float('inf') else -1


class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        n = len(jobDifficulty)
        
        def helper(i, d):
            if i == n and d == 0:
                return 0
            if d <= 0 or n - i < d:
                return float('inf')
            
            if (i, d) in memo:
                return memo[(i, d)]
            
            subGroupJobMax = -1
            memo[(i, d)] = float('inf')
            for j in range(i, n):
                subGroupJobMax = max(subGroupJobMax, jobDifficulty[j])
                result = subGroupJobMax + helper(j+1, d-1)
                memo[(i, d)] = min(memo[(i, d)], result)
            return memo[(i, d)]
            
        memo = {}
        ans = helper(0, d)
        return -1 if ans is None or ans == float('inf') else ans
            


class Solution:
    def minDifficulty(self, A: List[int], d: int) -> int:
        n = len(A)
        
        if d>n: #more days than job
            return -1
        
        dp = [[math.inf]*(d+1) for _ in range(n)]
        #dp[i][j] store the ans for jobs i:n with j days remaining
        
        for i in range(n-1,-1,-1):
            for j in range(1,d+1):
                if n-i<j: #more days than jobs
                    continue
                rMax = -math.inf
                for k in range(i,n-j+1): #if we finish k jobs today
                    rMax=max(rMax,A[k])
                    if j==1:
                        dp[i][j]=rMax
                    else:
                        dp[i][j] = min(dp[i][j],rMax+dp[k+1][j-1])
        return dp[0][d]
                    


class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        @lru_cache(None)
        def find_schedule(remaining_days, task_start):
            if remaining_days == 0:
                return max(jobDifficulty[task_start:])
            
            total = float('inf')
            cur_diff = jobDifficulty[task_start]
            for i in range(task_start, len(jobDifficulty) - remaining_days):
                cur_diff = max(cur_diff, jobDifficulty[i])
                total = min(total, cur_diff + find_schedule(remaining_days - 1, i+1))
            return total
        
        if len(jobDifficulty) < d:
            return -1
        return find_schedule(d-1, 0)


class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        if len(jobDifficulty) < d:
            return -1
        maxTable = [0] * len(jobDifficulty)
        maxTable[-1] = jobDifficulty[-1]
        for i in range(len(jobDifficulty)-2,-1,-1):
            maxTable[i] = max(maxTable[i+1], jobDifficulty[i])
        
        def dfs(i, d, visit):
            if i == len(jobDifficulty):
                return float('inf')
            if d == 1:
                return maxTable[i]
            if (i, d) in visit:
                return visit[(i,d)]
            
            res = float('inf')
            cur = 0
            for j in range(i, len(jobDifficulty)):
                cur = max(cur, jobDifficulty[j])
                res = min(res, cur + dfs(j+1, d-1, visit))
            visit[(i,d)] = res
            return res
        return dfs(0,d,{})

class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        N = len(jobDifficulty)
        @lru_cache(None)
        def dfs(index, days_left, curr_max):
            if index == N:
                if days_left == 0:
                    return curr_max
                else:
                    return float('inf')
            
            res = float('inf')
            same_day = dfs(index + 1, days_left, max(curr_max, jobDifficulty[index]))
            diff_day = dfs(index + 1, days_left - 1, jobDifficulty[index]) + curr_max
            
            res = min(same_day, diff_day)
            
            return res
    
        res = dfs(0, d, 0)
        
        if res == float('inf'):
            return -1
        else:
            return res

class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        n = len(jobDifficulty)
        if d > n:
            return -1
        dp = [[float('inf') for _ in range(d + 1)] for _ in range(n + 1)]
        dp[0][0] = 0
        for i in range(1, n+1):
            for k in range(1, d+1):
                md = 0
                for j in range(i-1, k-2, -1):
                    md = max(md, jobDifficulty[j])
                    dp[i][k] = min(dp[i][k], dp[j][k-1]+md)
        return dp[n][d]

class Solution:
    def minDifficulty(self, jD: List[int], d: int) -> int:
        if len(jD) < d: return -1
        memo = {}
        def dp(memo, jD, i, d): # 求解mD(jD[i:], d)
            if len(jD) - i  < d: return -1
            if d == 1: return max(jD[i:])
            if (i, d) in memo:
                return memo[(i, d)]
            ans, cur = 9999999999, 0
            for j in range(i, len(jD)): #遍历S(D_1)
                cur = max(cur, jD[j])
                x = dp(memo, jD, j + 1, d - 1)#核心代码 md(D_1^{rest}, d-1)
                if x != -1: 
                    ans = min(ans, cur + x)
            memo[(i, d)] = ans
            return ans
        return dp(memo, jD, 0, d)


class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        # self.res = sys.maxsize
        ht = {}
        res = self.dfs(jobDifficulty, d, ht)
        if res == sys.maxsize:
            return -1
        return res
    
    def dfs(self, nums, K, ht):
        if K == 1:
            if len(nums) == 0:
                return sys.maxsize
            return max(nums)
        key = (len(nums), K)
        if key in ht:
            return ht[key]
        res = sys.maxsize
        a = 0
        for i in range(len(nums)):
            a = max(a, nums[i])
            b = self.dfs(nums[i+1:], K-1, ht)
            if a + b < res:
                res = a + b
        ht[key] = res
        return res


class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        MAX = 300 * 1000 * 10
        N = len(jobDifficulty)
        cache = {}
        max_jobDifficulty = []
        for i in range(0, N):
            max_ij = [jobDifficulty[i]]
            for j in range(i+2, N+1):
                max_ij.append(max(max_ij[-1], jobDifficulty[j-1]))
            max_jobDifficulty.append(max_ij)
        def get_max_jobDifficulty(i, j):
            return max_jobDifficulty[i][j-i-1]
        def dp(left_days: int, left_jobs_i: int, current_jobs_i: int) -> int:
            key = (left_days, left_jobs_i, current_jobs_i)
            if key not in cache:
                n_left_jobs = N - left_jobs_i
                if n_left_jobs == 0:
                    assert left_days > 0
                    if left_days == 1 and current_jobs_i < left_jobs_i:
                        cost = get_max_jobDifficulty(current_jobs_i, left_jobs_i)
                    else:
                        cost = MAX
                elif n_left_jobs == left_days:
                    cost = get_max_jobDifficulty(current_jobs_i, left_jobs_i + 1) + sum(jobDifficulty[(left_jobs_i + 1):])
                else:
                    cost = dp(left_days, left_jobs_i + 1, current_jobs_i)
                    if left_days > 1:
                        cost = min(cost, dp(left_days - 1, left_jobs_i + 1, left_jobs_i + 1) + get_max_jobDifficulty(current_jobs_i, left_jobs_i + 1))
                cache[key] = cost
            return cache[key]
        ret = dp(d, 0, 0)
        if ret >= MAX:
            return -1
        return ret

import functools
class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        n = len(jobDifficulty)
        if n < d:
            return -1
        @functools.lru_cache(None)
        def dfs(i, d):
            if d==1:
                return max(jobDifficulty[i:])
            res, maxd = float('inf'), 0
            for j in range(i, n - d + 1):
                maxd = max(maxd, jobDifficulty[j])
                res = min(res, maxd + dfs(j + 1, d - 1))
            return res
        return dfs(0, d)

class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        MAX = 300 * 1000 * 10
        N = len(jobDifficulty)
        cache = {}
        max_jobDifficulty = []
        for i in range(0, N):
            max_ij = [jobDifficulty[i]]
            for j in range(i+2, N+1):
                max_ij.append(max(max_ij[-1], jobDifficulty[j-1]))
            max_jobDifficulty.append(max_ij)
        def get_max_jobDifficulty(i, j):
            return max_jobDifficulty[i][j-i-1]
        def dp(left_days: int, left_jobs_i: int, current_jobs_i: int) -> int:
            key = (left_days, left_jobs_i, current_jobs_i)
            if key not in cache:
                if left_jobs_i == N:
                    assert left_days > 0
                    if left_days == 1 and current_jobs_i < left_jobs_i:
                        cost = get_max_jobDifficulty(current_jobs_i, left_jobs_i)
                    else:
                        cost = MAX
                else:
                    cost = dp(left_days, left_jobs_i + 1, current_jobs_i)
                    if left_days > 1:
                        cost = min(cost, dp(left_days - 1, left_jobs_i + 1, left_jobs_i + 1) + get_max_jobDifficulty(current_jobs_i, left_jobs_i + 1))
                cache[key] = cost
            return cache[key]
        ret = dp(d, 0, 0)
        if ret >= MAX:
            return -1
        return ret

class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        MAX = 300 * 1000 * 10
        N = len(jobDifficulty)
        cache = {}
        max_jobDifficulty = []
        for i in range(0, N):
            max_ij = [jobDifficulty[i]]
            for j in range(i+2, N+1):
                max_ij.append(max(max_ij[-1], jobDifficulty[j-1]))
            max_jobDifficulty.append(max_ij)
        def get_max_jobDifficulty(i, j):
            return max_jobDifficulty[i][j-i-1]
        def dp(left_days: int, left_jobs_i: int, current_jobs_i: int) -> int:
            key = (left_days, left_jobs_i, current_jobs_i)
            if key not in cache:
                n_left_jobs = N - left_jobs_i
                if n_left_jobs == 0:
                    assert left_days > 0
                    if left_days == 1 and current_jobs_i < left_jobs_i:
                        cost = get_max_jobDifficulty(current_jobs_i, left_jobs_i)
                    else:
                        cost = MAX
                elif n_left_jobs == left_days:
                    cost = get_max_jobDifficulty(current_jobs_i, left_jobs_i + 1) + sum(jobDifficulty[(left_jobs_i + 1):])
                else:
                    cost = dp(left_days, left_jobs_i + 1, current_jobs_i)
                    if left_days > 1:
                        m = get_max_jobDifficulty(current_jobs_i, left_jobs_i + 1)
                        if m < cost:
                            cost = min(cost, dp(left_days - 1, left_jobs_i + 1, left_jobs_i + 1) + m)
                cache[key] = cost
            return cache[key]
        ret = dp(d, 0, 0)
        if ret >= MAX:
            return -1
        return ret

class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        MAX = 300 * 1000 * 10
        N = len(jobDifficulty)
        cache = {}
        max_jobDifficulty = []
        for i in range(0, N):
            max_ij = [jobDifficulty[i]]
            for j in range(i+2, N+1):
                max_ij.append(max(max_ij[-1], jobDifficulty[j-1]))
            max_jobDifficulty.append(max_ij)
        def get_max_jobDifficulty(i, j):
            return max_jobDifficulty[i][j-i-1]
        def dp(left_days: int, left_jobs_i: int, current_jobs_i: int) -> int:
            key = (left_days, left_jobs_i, current_jobs_i)
            if key not in cache:
                n_left_jobs = N - left_jobs_i
                if n_left_jobs == 0:
                    assert left_days > 0
                    if left_days == 1 and current_jobs_i < left_jobs_i:
                        cost = get_max_jobDifficulty(current_jobs_i, left_jobs_i)
                    else:
                        cost = MAX
                elif n_left_jobs == left_days:
                    cost = get_max_jobDifficulty(current_jobs_i, left_jobs_i + 1) + sum(jobDifficulty[(left_jobs_i + 1):])
                elif n_left_jobs < left_days:
                    cost = MAX
                else:
                    cost = dp(left_days, left_jobs_i + 1, current_jobs_i)
                    if left_days > 1:
                        cost = min(cost, dp(left_days - 1, left_jobs_i + 1, left_jobs_i + 1) + get_max_jobDifficulty(current_jobs_i, left_jobs_i + 1))
                cache[key] = cost
            return cache[key]
        ret = dp(d, 0, 0)
        if ret >= MAX:
            return -1
        return ret

class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        mem = {}
        maxMem = {}
        sumMem = []
        for i, diff in enumerate(jobDifficulty):
            if i==0:
                sumMem.append(diff)
            else:
                sumMem.append(sumMem[-1]+diff)
        
        def maxHelper(i, j):
            if (i, j) in maxMem:
                return maxMem[(i,j)]
            
            maxVal = 0
            for index in range(i, j):
                if jobDifficulty[index]>maxVal:
                    maxVal = jobDifficulty[index]
            maxMem[(i, j)] = maxVal
            return maxVal

        def helper(jobNum, days):
            if (jobNum, days) in mem:
                return mem[(jobNum, days)]

            if jobNum < days:
                return float('inf')

            elif jobNum == days:
                minCplx = sumMem[jobNum-1]

            elif days == 1:
                minCplx = maxHelper(0, jobNum)

            else:
                minCplx = float('inf')
                for i in range(days-1, jobNum):
                    curCplx = helper(i, days-1) + maxHelper(i, jobNum)
                    if curCplx<minCplx:
                        minCplx = curCplx

            mem[(jobNum, days)] = minCplx
            return minCplx

        res = helper(len(jobDifficulty), d)
        return -1 if res == float('inf') else res
        


class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        mem = {}
        maxMem = {}
        
        def maxHelper(i, j):
            if (i, j) in maxMem:
                return maxMem[(i,j)]
            
            maxVal = 0
            for index in range(i, j):
                if jobDifficulty[index]>maxVal:
                    maxVal = jobDifficulty[index]
            maxMem[(i, j)] = maxVal
            return maxVal

        def helper(jobNum, days):
            if (jobNum, days) in mem:
                return mem[(jobNum, days)]

            if jobNum < days:
                return float('inf')

            elif jobNum == days:
                minCplx = sum(jobDifficulty[:jobNum])

            elif days == 1:
                minCplx = maxHelper(0, jobNum)

            else:
                minCplx = float('inf')
                for i in range(days-1, jobNum):
                    curCplx = helper(i, days-1) + maxHelper(i, jobNum)
                    if curCplx<minCplx:
                        minCplx = curCplx

            mem[(jobNum, days)] = minCplx
            return minCplx

        res = helper(len(jobDifficulty), d)
        return -1 if res == float('inf') else res
        


class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        
        n = len(jobDifficulty)
        memo = {}
        
        if d > n:
            return -1
        if d == n:
            return sum(jobDifficulty)
        
        def dfs(i, diff, days):
            if i == n:
                return diff if days == 0 else float('inf')
            
            if (i, diff, days) in memo:
                return memo[(i, diff, days)]
            
            max_effort = max(diff, jobDifficulty[i])
            
            s1 = max_effort + dfs(i+1, 0, days-1)
            s2 = dfs(i+1, max_effort, days)
            
            memo[(i, diff, days)] = min(s1, s2)
            
            return memo[(i, diff, days)]
        
        return dfs(0, 0, d)

class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        n = len(jobDifficulty)
        dp = {}
        myIntMax = 10000000
        
        def findMinDif(jobIdx, daysLeft):
            if daysLeft<0:
                return -1
            if jobIdx==n and daysLeft>0:
                return -1
            if jobIdx==n and daysLeft==0:
                return 0
            
            if str(jobIdx)+str(daysLeft) in dp:
                return dp[str(jobIdx)+str(daysLeft)]
            
            todayDiff = 0 
            totalDiff = myIntMax
            
            for idx in range(jobIdx,n):
                todayDiff = max(todayDiff, jobDifficulty[idx])
                nextDiff = findMinDif(idx+1, daysLeft-1)                
                dp[str(idx+1)+str(daysLeft-1)] = nextDiff
                
                if nextDiff != -1:                    
                    totalDiff = min(totalDiff, todayDiff + nextDiff)
                else:
                    break
                
            
            return totalDiff
        
        ret = findMinDif(0,d)
        if ret == myIntMax:
            return -1
        else:
            return ret


class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        if len(jobDifficulty) < d:
            return -1
        
        def dfs(i, d, visit):
            if i == len(jobDifficulty):
                return float('inf')
            if d == 1:
                return max(jobDifficulty[i:])
            if (i, d) in visit:
                return visit[(i,d)]
            
            res = float('inf')
            cur = 0
            for j in range(i, len(jobDifficulty)):
                cur = max(cur, jobDifficulty[j])
                res = min(res, cur + dfs(j+1, d-1, visit))
            visit[(i,d)] = res
            return res
        return dfs(0,d,{})

from functools import lru_cache
class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        
        
        dumb = 99999999999
        lim = len(jobDifficulty)
        @lru_cache(None)
        def r(i,day):
            if day==d-1:return max(jobDifficulty[i:])
            
            if i==lim-1 and day<d-1: return dumb
            
            else:
                
                tmp = []
                for j in range(i+1,lim):
                    tmp.append(max(jobDifficulty[i:j])+r(j,day+1))

                return min(tmp)
        
        val = r(0,0)
        if val>dumb:return -1
        return val

class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        
        from functools import lru_cache
        @lru_cache(None)
        def helper(st, d):
            if st == len(jobDifficulty) or d == 0 or len(jobDifficulty) - st < d:
                return math.inf
            if d==1:
                return max(jobDifficulty[st:])
            mn=float('inf')
            for i in range(st+1, len(jobDifficulty)-d+2):
                s = max(jobDifficulty[st:i])+helper(i,d-1)
                mn = min(s, mn)
            return mn
        res = helper(0, d)
        return res if res!=float('inf') else -1
                


class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        n = len(jobDifficulty)
        if n < d:
            return -1
        @lru_cache(None)
        def go(l, day):
            if l >= n:
                return math.inf
            if day == d:
                return max(jobDifficulty[l:])
            ans = math.inf
            for i in range(l, n):
                ans = min(ans, go(i+1, day+1) + max(jobDifficulty[l:i+1]))
            return ans
        return go(0, 1)


class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        
        from functools import lru_cache
        @lru_cache(None)
        def helper(st, d):
            if d==1:
                return max(jobDifficulty[st:])
            mn=float('inf')
            for i in range(st+1, len(jobDifficulty)-d+2):
                s = max(jobDifficulty[st:i])+helper(i,d-1)
                mn = min(s, mn)
            return mn
        res = helper(0, d)
        return res if res!=float('inf') else -1
                


from functools import lru_cache
class Solution:
    def minDifficulty(self, A, d):
        # n = len(A)
        # dp, dp2 = [math.inf] * n, [0] * n
        # if n < d: return -1
        # for d in range(d):
        #     stack = []
        #     for i in range(d, n):
        #         dp2[i] = dp[i - 1] + A[i] if i else A[i]
        #         while stack and A[stack[-1]] <= A[i]:
        #             j = stack.pop()
        #             dp2[i] = min(dp2[i], dp2[j] - A[j] + A[i])
        #         if stack:
        #             dp2[i] = min(dp2[i], dp2[stack[-1]])
        #         stack.append(i)
        #     dp, dp2 = dp2, [0] * n
        # return dp[-1]
        
        n = len(A)
        if n < d: return -1
        
        @lru_cache(None)
        def dp(n, d):

            if n < d: return math.inf
            if d == 1: return max(A[:n])          
            return min(dp(t, d - 1) + max(A[t : n]) for t in range(n))
        
        return dp(n, d)
        


class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        @lru_cache(None)
        def helper(start, d):
            if len(jobDifficulty) - start < d:
                return float('inf')
            if d == 1:
                return max(jobDifficulty[start:])
            result = float('inf')
            for i in range(start, len(jobDifficulty) - d + 1):
                result = min(result, max(jobDifficulty[start:i+1]) + helper(i+1, d-1))
            return result
        result = helper(0, d)
        return result if result != float('inf') else -1

class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        @lru_cache(None)
        def helper(i,d):
            if(d==1):
                if(len(jobDifficulty)==0):
                    return float('inf')
                return max(jobDifficulty[i:])
            else:
                m=float('inf')
                for j in range(i+1,len(jobDifficulty)-d+2):
                    m=min(max(jobDifficulty[i:j])+helper(j,d-1),m)
                return m
        x=helper(0,d)
        if(x==float('inf')):
            return -1
        else:
            return x
            
        


class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        
        n = len(jobDifficulty)
        
        if n < d:
            return -1
        
        dp = [[-1 for i in range(d+1)] for j in range(n)]
        
        def helper(i, days):

            nonlocal dp

            if dp[i][days] != -1:
                return dp[i][days]
            
            
            if days == 1:
                dp[i][days] = max(jobDifficulty[i:])
            else:
                dp[i][days] = min([max(jobDifficulty[i:i+j]) + helper(i+j, days-1) for j in range(1, n-days-i+2)])
                
            return dp[i][days]
        
        return helper(0, d)


class Solution:
    def minDifficulty(self, JD: List[int], d: int) -> int:
        n = len(JD)
        @lru_cache(None)
        def dp(i, k):
            if k == 1 and i!=n: return max(JD[i:])
            if k == 0 and i == n: return 0
            if k == 0 or i == n: return math.inf
            ans = math.inf
            for j in range(i, n):
                ans = min(ans, max(JD[i:j+1]) + dp(j+1, k-1))
            return ans
        return dp(0, d) if dp(0, d) != math.inf else -1

class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        n = len(jobDifficulty)
        if d > n:
            return -1
        
        @lru_cache(None)
        def dp(start, k):
            
            if k == 1:
                return max(jobDifficulty[start:])
            
            minvalue = float('inf')
            for i in range(start+1, n):
                left = max(jobDifficulty[start:i])
                right = dp(i, k-1)
                
                minvalue = min(minvalue, left+right)
            
            return minvalue
        
        return dp(0,d)


class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        mem = {}
        n = len(jobDifficulty)
        if n < d:
            return -1
        def get_dp(i, j):
            if (i, j) not in mem:
                if j == d:
                    mem[i, j] = max(jobDifficulty[i:])
                else:
                    mem[i, j] = min(max(jobDifficulty[i:i+k]) + get_dp(i+k, j+1) for k in range(1, n-i-d+j+1))
            return mem[i, j]
        return get_dp(0, 1)

class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        def search(jobs: List[int], index: int, d: int) -> int:
            if len(jobs) - index < d:
                return -1
            if (d, index) in memo:
                return memo[(d, index)]
            if d == 1:
                memo[(d, index)] = max(jobs[index:])
                return memo[(d, index)]
            result = float('inf')
            for i in range(index, len(jobs) - d + 1):
                result = min(result, max(jobs[index: i + 1]) + search(jobs, i + 1, d - 1))
            memo[(d, index)] = result
            return result
        
        memo = {}
        return search(jobDifficulty, 0, d)


class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        n = len(jobDifficulty)        
        dp=[]
        for a in range(d+1):
            dp.append([-1]*(n+1))
        
        #print(dp)
        
        def helper(jobD, n, d, dp):
            if n < d:
                return -1
            #print(n,d, len(dp))
            if dp[d][n] != -1:
                return dp[d][n]
            if d == n:
                dp[d][n] = sum(jobD[0:n])
                return dp[d][n]
            if d == 1:
                dp[d][n] = max(jobD[0:n])
                return dp[d][n]
            for i in range(1, n):
                r = helper(jobD, i, d-1, dp)
                if r != -1:
                    if dp[d][n] == -1:
                        dp[d][n] = r + max(jobD[i:n])
                    else:
                        dp[d][n] = min(dp[d][n], r + max(jobD[i:n]))
                    #print(dp[d][n], d, n)
            return dp[d][n]
    
        r =  helper(jobDifficulty, n, d, dp)
        #print(dp)
        return r

class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        n = len(jobDifficulty)
        if d > n:
            return -1;
        if d == n:
            return sum(jobDifficulty)
        
        dp=[]
        for a in range(d+1):
            dp.append([-1]*(n+1))
        
        #print(dp)
        
        def helper(jobD, n, d, dp):
            if n < d:
                return -1
            #print(n,d, len(dp))
            if dp[d][n] != -1:
                return dp[d][n]
            if d == n:
                dp[d][n] = sum(jobD[0:n])
                return dp[d][n]
            if d == 1:
                dp[d][n] = max(jobD[0:n])
                return dp[d][n]
            for i in range(1, n):
                r = helper(jobD, i, d-1, dp)
                if r != -1:
                    if dp[d][n] == -1:
                        dp[d][n] = r + max(jobD[i:n])
                    else:
                        dp[d][n] = min(dp[d][n], r + max(jobD[i:n]))
                    #print(dp[d][n], d, n)
            return dp[d][n]
    
        r =  helper(jobDifficulty, n, d, dp)
        #print(dp)
        return r

class Solution:
    def minDifficulty(self, jobs: List[int], d: int) -> int:
        n = len(jobs)
        dp = [[math.inf] * n for _ in range(d)]
        
        max_job = 0
        for job in range(n):
            max_job = max(max_job, jobs[job])
            dp[0][job] = max_job
        
        for day in range(1, d):
            for last_job in range(day, n):
                dp[day][last_job] = min(
                    (dp[day - 1][first_job - 1] + max(jobs[first_job:last_job + 1])
                    for first_job in range(day, last_job + 1)),
                    default=math.inf
                )
        
        return dp[-1][-1] if dp[-1][-1] != math.inf else -1


import functools


class Solution:

    def minDifficulty(self, A, d):
        if len(A) < d:
            return -1

        @functools.lru_cache(None)
        def dfs(i, d):
            if d == 1:
                return max(A[i:])
            res = float('inf')
            max_cost_current_day = 0
            for j in range(i, len(A) - d + 1):
                # i'm percorring the array and trying all possibilites
                # the cost of a day is the max task on it
                max_cost_current_day = max(max_cost_current_day, A[j])
                # res = current_day_cost + others_days cost
                res = min(res, max_cost_current_day + dfs(j + 1, d - 1))
            return res
        return dfs(0, d)


class Solution:
    def minDifficulty(self, jobs: List[int], d: int) -> int:
        n = len(jobs)
        dp = [[math.inf] * n for _ in range(d)]
        
        max_job = 0
        for job in range(n):
            max_job = max(max_job, jobs[job])
            dp[0][job] = max_job
        
        for day in range(1, d):
            for last_job in range(day, n):
                dp[day][last_job] = min(
                    dp[day - 1][first_job - 1] + max(jobs[first_job:last_job + 1])
                    for first_job in range(day, last_job + 1)
                )
        
        return dp[-1][-1] if dp[-1][-1] != math.inf else -1

class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        n = len(jobDifficulty)
        if n < d:
            return -1
        if n == d:
            return sum(jobDifficulty)
        
        dp = [[float('inf')] * (n + 1) for _ in range(d + 1)]
        for i in range(1, n + 1):
            dp[1][i] = max(jobDifficulty[:i])
            
        for _d in range(2, d + 1):
            for i in range(_d, n + 1):
                for j in range(_d - 1, i):
                    dp[_d][i] = min(dp[_d][i], dp[_d - 1][j] + max(jobDifficulty[j:i]))
                    
        return dp[d][n]

class Solution:
    def minDifficulty(self, jobs: List[int], d: int) -> int:
        n = len(jobs)
        dp = [[math.inf] * n for _ in range(d)]
        
        max_job = 0
        for job in range(n):
            max_job = max(max_job, jobs[job])
            dp[0][job] = max_job
        
        for day in range(1, d):
            for job in range(day, n):
                cur = math.inf
                for prev in range(day, job + 1):
                    max_job = max(jobs[prev:job+1])
                    cur = min(cur, dp[day - 1][prev - 1] + max_job)
                dp[day][job] = cur
        
        return dp[-1][-1] if dp[-1][-1] != math.inf else -1

class Solution:
    def minDifficulty(self, jobDifficulty, d):
        '''
        :type jobDifficulty: List[int]
        :type d: int
        :rtype: int
        '''
        njobs = len(jobDifficulty)
        if njobs < d: return -1

        dp = [[float('inf')] * njobs for _ in range(d)]
        # base case - complete first j jobs using 1 day
        for j in range(njobs):
            dp[0][j] = max(jobDifficulty[:j+1])

        for i in range(1, d):
            for j in range(i, njobs):
                for k in range(i, j+1):
                    dp[i][j] = min(dp[i][j], dp[i-1][k-1] + max(jobDifficulty[k:j+1]))
        return dp[d-1][njobs-1]


class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        size = len(jobDifficulty)
        memoi = [jobDifficulty[0]] * size
        for i in range(1, size):
            memoi[i] = max(memoi[i-1], jobDifficulty[i])
        for cut in range(1, d):
            newMemoi = [float('inf')] * size
            for end in range(cut, size):
                for split in range(cut - 1, end):
                    newMemoi[end] = min(
                        newMemoi[end],
                        memoi[split] + max(jobDifficulty[split+1:end+1])
                    )
            memoi = newMemoi
        return memoi[-1] if memoi[-1] != float('inf') else -1


class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        # two dimensional dp
        # dp[m][n]  n<=m   the best solution when there are m+1 jobs in n+1 days
        # dp[m][n] =min(dp[j][n-1] + max(jobDifficulty[j+1:m+1]))  n-1<= j <= m-1
        
        if len(jobDifficulty) < d:
            return -1
        dp= [[0 for i in range(d)] for j in range(len(jobDifficulty))]
        for j in range(len(jobDifficulty)):
            dp[j][0] = max(jobDifficulty[:j+1])
        for day in range(1,d):
            for i in range(day,len(jobDifficulty)):
                dpValue = sum(jobDifficulty)
                for j in range(day-1,i):
                    dpValue  = min(dpValue, dp[j][day-1]+max(jobDifficulty[j+1:i+1]))
                dp[i][day] = dpValue
        return dp[len(jobDifficulty)-1][d-1]


class Solution:
    def minDifficulty(self, jobDifficulty, d):
        '''
        :type jobDifficulty: List[int]
        :type d: int
        :rtype: int
        '''
        njobs = len(jobDifficulty)
        if njobs < d: return -1

        dp = [[float('inf')] * njobs for _ in range(d)]
        # base case
        for j in range(njobs):
            dp[0][j] = max(jobDifficulty[:j+1])

        for i in range(1, d):
            for j in range(i, njobs):
                for k in range(i, j+1):
                    dp[i][j] = min(dp[i][j], dp[i-1][k-1] + max(jobDifficulty[k:j+1]))
        return dp[d-1][njobs-1]


class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        #0928
        #dp(i,k)=到jobDifficulty[i]为止的job（共i+1个），使用k天完成的 minimum difficulty 
        if len(jobDifficulty)<d:
            return -1
        dp = [[10000]*(d+1) for i in range(len(jobDifficulty ))]
        dp[0][1]=jobDifficulty[0]
        for i in range(len(jobDifficulty)):
            for k in range(1,d+1):
                # print(\"i,\",i,\"k,\",k)
                if k==1:
                    dp[i][k]=max(jobDifficulty[:i+1])
                    continue
                if k > i+1 or (i==0 and k==1):
                    # print(\"continue\")
                    continue
                mind=10000
                for j in range(0, i):
                    # print(\"j=\",j,dp[j][k-1])
                    mind=min(dp[j][k-1]+max(jobDifficulty[j+1:i+1]), mind)
                    # print(\"mind\",mind)
                dp[i][k]=mind
        print(dp)
        return dp[-1][-1]
        


class Solution:
    def dfs(self, jobDifficulty, start_day, d, memo):
        if d == 1:
            return max(jobDifficulty[start_day:])

        if (start_day, d) in memo:
            return memo[(start_day, d)]
        
        min_diff = float('inf')

        for i in range(start_day, len(jobDifficulty) - d + 1):
            min_diff = min(min_diff, max(jobDifficulty[start_day:i+1]) + self.dfs(jobDifficulty, i + 1, d - 1, memo))
        
        memo[(start_day, d)] = min_diff
        return min_diff

    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        if len(jobDifficulty) < d:
            return -1

        memo = collections.defaultdict(int)
        return self.dfs(jobDifficulty, 0, d, memo)

class Solution:
    
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        
       
        llen = len(jobDifficulty)
        if d>llen:
            return -1
        if llen==1:
            return jobDifficulty[0]
        dct = [[float('inf') for _ in range(d+1)] for _ in range(llen+1)]
 
            
     
                
        
        for i in range(1, llen+1):
            for j in range(1,d+1):
                if j == 1:
                    dct[i][1] = max(jobDifficulty[:i])
                    continue
                elif i < j:
                    continue
                for k in range(1,i):
                    dct[i][j] = min(dct[i][j], dct[k][j-1]+max(jobDifficulty[k:i]))
                    
        return dct[llen][d]
                    
                    


class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        if len(jobDifficulty) < d:
            return -1
        
        self.cache = {}
        return self.helper(jobDifficulty, d, 0)
        
    def helper(self, jobDifficulty: List[int], d: int, start: int) -> int:
        if d == 1:
            return max(jobDifficulty[start:])
        
        if (d, start) not in self.cache:
            self.cache[(d, start)] = min(
                [
                    max(jobDifficulty[start:end]) + self.helper(jobDifficulty, d-1, end) 
                    for end in range(start+1, len(jobDifficulty)-d+2)
                ]
            )
        
        return self.cache[(d, start)]


class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        # @lru_cache(None)
        # def helper(start, d):
        #     if len(jobDifficulty) - start < d:
        #         return float('inf')
        #     if d == 1:
        #         return max(jobDifficulty[start:])
        #     result = float('inf')
        #     for i in range(start, len(jobDifficulty) - d + 1):
        #         result = min(result, max(jobDifficulty[start:i+1]) + helper(i+1, d-1))
        #     return result
        # result = helper(0, d)
        # return result if result != float('inf') else -1
        if len(jobDifficulty) < d:
            return -1
        dp = [[float('inf')] * (d + 1) for _ in range(len(jobDifficulty))]
        tempmax = 0
        for i, job in enumerate(jobDifficulty):
            tempmax = max(tempmax, job)
            dp[i][1] = tempmax
        for day in range(2, d+1):
            for j in range(day-1, len(jobDifficulty)+1):
                result = float('inf')
                for k in range(j-1):
                    result = min(result, dp[k][day-1] + max(jobDifficulty[k+1:j]))
                dp[j-1][day] = result
        return dp[-1][-1]


class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        if len(jobDifficulty) < d:
            return -1
        
        return self.topdown(jobDifficulty, d, 0, {})
    
    def topdown(self, job, d, index, memo):
        if d <=0:
            return flot('inf')
        
        if d == 1:
            if index < len(job):
                return max(job[index:])
            return float('inf')
        
        if (d, index) in memo:
            return memo[(d,index)]
        
        minDiff = float('inf')
        
        for i in range(index, len(job)):
            minDiff = min(minDiff, self.topdown(job, d-1, i+1, memo) + max(job[index:i+1]))
        
        memo[(d, index)] = minDiff
        
        return minDiff
        


class Solution:
    def minDifficulty(self, jobs: List[int], d: int) -> int:
        if len(jobs) < d:
            return -1
        
        return self.topDown(jobs, d, 0, {})
    
    def topDown(self, jobs, d, index, memo):
        if d <= 0:
            return float('inf')
        # if len(jobs) - index + 1 < d:
        #     return float('inf')
        if d == 1:
            if index < len(jobs):
                return max(jobs[index: ])
            return float('inf')
        
        if (d, index) in memo:
            return memo[(d, index)]
        
        mindiff = float('inf')
        
        for i in range(index, len(jobs)):
            mindiff = min(mindiff, self.topDown(jobs, d - 1, i + 1, memo) + max(jobs[index : i + 1]))
        memo[(d, index)] = mindiff
        return mindiff

class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        if d > len(jobDifficulty): return -1
        m = len(jobDifficulty)
        dp = [float('inf') for _ in range(m)]
        dp[0] = jobDifficulty[0]
        for i in range(1, m): dp[i] = max(dp[i - 1], jobDifficulty[i])
        for i in range(1, d):
            for j in range(m - 1, i - 1, -1):
                dp[j] = float('inf')
                val = 0
                for k in range(j, i - 1, -1):
                    val = max(jobDifficulty[k], val)
                    dp[j] = min(dp[j], dp[k - 1] + val)
        # print(dp)
        return dp[-1]


class Solution:
    
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        
       
        llen = len(jobDifficulty)
        if d>llen:
            return -1
        if llen==1:
            return jobDifficulty[0]
        dct = [[float('inf') for _ in range(d+1)] for _ in range(llen+1)]
 
            
            
        for i in range(1,llen+1):
            dct[i][1] = max(jobDifficulty[:i])
                
        
        for i in range(2, llen+1):
            for j in range(2,d+1):
                for k in range(1,i):
                    dct[i][j] = min(dct[i][j], dct[k][j-1]+max(jobDifficulty[k:i]))
                    
        return dct[llen][d]
                    
                    


class Solution:
    
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        
        l = jobDifficulty
        llen = len(l)
        if d>llen:
            return -1
        if llen==1:
            return l[0]
        dct = [[float('inf') for _ in range(d+1)] for _ in range(llen+1)]
 
            
            
        for i in range(1,llen+1):
            dct[i][1] = max(l[:i])
                
        
        for i in range(2, llen+1):
            for j in range(2,d+1):
                for k in range(1,i):
                    dct[i][j] = min(dct[i][j], dct[k][j-1]+max(l[k:i]))
                    
        return dct[llen][d]
                    
                    


class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int: 
        if len(jobDifficulty) < d:
            return -1 
        return self.top_down(jobDifficulty, d, 0, {})
    
    def top_down(self, jobs, d, index, memo):
        if d <= 0:
            return float('inf')
        if d == 1:
            if index < len(jobs):
                return max(jobs[index:])
            return float('inf')
        if (d, index) in memo:
            return memo[(d, index)]
        min_diff = float('inf')
        for i in range(index, len(jobs)):
            min_diff = min(min_diff, self.top_down(jobs, d-1, i+1, memo) + max(jobs[index:i+1]))
        memo[(d, index)] = min_diff
        return min_diff

'''
Time Complexity : O(n * d) where n = len(jobs)
'''
class Solution:
    def minDifficulty(self, jobs: List[int], d: int) -> int:
        if len(jobs) < d:
            return -1
        
        return self.topDown(jobs, d, 0, {})
    
    def topDown(self, jobs, d, index, memo):
        #This should never be the case as we schedule all
        #the rest of jobs on d = 1
        if d <= 0:
            return float('inf')
        # if len(jobs) - index + 1 < d:
        #     return float('inf')
        if d == 1:
            #if we still have some jobs on d = 1
            if index < len(jobs):
                return max(jobs[index: ])
            #If left with no job, we violate \"atleast a task every day\"
            return float('inf')
        
        if (d, index) in memo:
            return memo[(d, index)]
        
        mindiff = float('inf')
        
        #Each day allocate jobs from 0-th index to i-th index,so
        #difficulty for that day is max(jobs[index:i+1]), then
        #recurse for d-1 days and jobs[i+1:]
        #Finally, see which combination gives the minimum difficulty
        for i in range(index, len(jobs)):
            mindiff = min(mindiff, self.topDown(jobs, d - 1, i + 1, memo) + max(jobs[index : i + 1]))
        memo[(d, index)] = mindiff
        
        return mindiff
        


class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        n = len(jobDifficulty)
        if n < d:
            return -1
        dp = [[math.inf for i in range(n)] for j in range(d)]
        for i in range(n):
            if i == 0:
                dp[0][0] = jobDifficulty[i]
            else:
                dp[0][i] = max(dp[0][i-1], jobDifficulty[i])
        for i in range(1,d):
            for j in range(i,n):
                for k in range(j):
                    dp[i][j] = min(dp[i][j], dp[i-1][k]+max(jobDifficulty[k+1:j+1]))
        #print(dp)
        return dp[-1][-1]
                
#         def go(l, day):
#             if l >= n:
#                 return math.inf
#             if day == d:
#                 return max(jobDifficulty[l:])
#             ans = math.inf
#             for i in range(l, n):
#                 ans = min(ans, go(i+1, day+1) + max(jobDifficulty[l:i+1]))
#             return ans
#         return go(0, 1)


class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        jobs = len(jobDifficulty)
        if jobs < d:
            return -1
        
        opt = [[float('inf')] * jobs for _ in range(d)]
        opt[0][0] = jobDifficulty[0]
        for i in range(1, min(jobs, d)):
            opt[i][i] = opt[i-1][i-1] + jobDifficulty[i]
        for i in range(1, jobs):
            opt[0][i] = max(opt[0][i-1], jobDifficulty[i])
        
        for k in range(1, jobs):
            for i in range(1, d):
                for x in range(1, k-i+2):  # k-x >= i-1
                    opt[i][k] = min(opt[i][k], 
                                   opt[i-1][k-x] + max(jobDifficulty[k-x+1: k+1]))
        return opt[d-1][jobs-1]

class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        jobs = len(jobDifficulty)
        if jobs < d:
            return -1
        
        opt = [[float('inf')] * jobs for _ in range(d)]
        opt[0][0] = jobDifficulty[0]
        for i in range(1, min(jobs, d)):
            opt[i][i] = opt[i-1][i-1] + jobDifficulty[i]
        for i in range(1, jobs):
            opt[0][i] = max(opt[0][i-1], jobDifficulty[i])
        print(opt)
        
        for k in range(1, jobs):
            for i in range(1, d):
                for x in range(1, k-i+2):  # k-x >= i-1
                    opt[i][k] = min(opt[i][k], 
                                   opt[i-1][k-x] + max(jobDifficulty[k-x+1: k+1]))
        print(opt)
        return opt[d-1][jobs-1]

from typing import List


class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:

        memo = {}

        def top_down(days_remaining, current_job_index):
            if days_remaining <= 0:
                return float('inf')
            if current_job_index >= len(jobDifficulty):
                return float('inf')
            if days_remaining == 1:
                return max(jobDifficulty[current_job_index:])
            if (days_remaining, current_job_index) in memo:
                return memo[(days_remaining, current_job_index)]
            min_cost = float('inf')
            for next_job_index in range(current_job_index+1, len(jobDifficulty)):
                min_cost = min(min_cost, max(
                    jobDifficulty[current_job_index:next_job_index])+top_down(days_remaining-1, next_job_index))
            memo[(days_remaining, current_job_index)] = min_cost
            return min_cost

        min_cost = top_down(d,0)
        return min_cost if min_cost != float('inf') else -1

class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int: 
        n = len(jobDifficulty)
        if n < d:
            return -1 
        memo = {}
        
        def top_down(subsets_remaining, index):
            nonlocal jobDifficulty, n, memo
            if subsets_remaining <= 0:
                return float('inf')
            if subsets_remaining == 1:
                if index < n:
                    return max(jobDifficulty[index:])
                return float('inf')
            if (subsets_remaining, index) in memo:
                return memo[(subsets_remaining, index)]
            min_difficulty = float('inf')
            for i in range(index, n):
                current_max = max(jobDifficulty[index:i+1])
                remaining_difficulty = top_down(subsets_remaining-1, i+1)
                min_difficulty = min(min_difficulty, current_max + remaining_difficulty)
            memo[(subsets_remaining, index)] = min_difficulty
            return min_difficulty
    
        return top_down(d, 0)


class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        if len(jobDifficulty) < d:
            return -1
        
        return self.topDown(jobDifficulty, d, 0, {})
    
    def topDown(self, jobs, d, index, memo):
        if d <= 0:
            return float('inf')
        # if len(jobs) - index + 1 < d:
        #     return float('inf')
        if d == 1:
            if index < len(jobs):
                return max(jobs[index: ])
            return float('inf')
        
        if (d, index) in memo:
            return memo[(d, index)]
        
        mindiff = float('inf')
        
        for i in range(index, len(jobs)):
            mindiff = min(mindiff, self.topDown(jobs, d - 1, i + 1, memo) + max(jobs[index : i + 1]))
        memo[(d, index)] = mindiff
        return mindiff


class Solution:
    def minDifficulty(self, jobs: List[int], d: int) -> int:
        if len(jobs) < d:
            return -1
        
        return self.topDown(jobs, d, 0, {})
    
    def topDown(self, jobs, d, index, memo):
        if d <= 0:
            return float('inf')
        # if len(jobs) - index + 1 < d:
        #     return float('inf')
        if d == 1:
            if index < len(jobs):
                return max(jobs[index: ])
            return float('inf')
        if (d, index) in memo:
            return memo[(d, index)]
        
        mindiff = float('inf')
        
        for i in range(index, len(jobs)):
            mindiff = min(mindiff, self.topDown(jobs, d - 1, i + 1, memo) + max(jobs[index : i + 1]))
        memo[(d, index)] = mindiff
        return mindiff


class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        if len(jobDifficulty) < d:
            return -1
        
        return self.topDown(jobDifficulty, d, 0, {})
    
    def topDown(self, jobs, d, index, memo):
        if d <= 0:
            return float('inf')
        # if len(jobs) - index + 1 < d:
        #     return float('inf')
        if d == 1:
            if index < len(jobs):
                return max(jobs[index: ])
            return float('inf')
        
        if (d, index) in memo:
            return memo[(d, index)]
        
        mindiff = float('inf')
        
        for i in range(index, len(jobs)):
            mindiff = min(mindiff, self.topDown(jobs, d - 1, i + 1, memo) + max(jobs[index : i + 1]))
        memo[(d, index)] = mindiff
        return mindiff

class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        if len(jobDifficulty) < d:
            return -1
        dp = [[float('inf') for i in range(len(jobDifficulty))] for j in range(d)]
        for i in range(len(jobDifficulty)):
            dp[0][i] = max(jobDifficulty[:i+1])
        for i in range(1,d):
            for j in range(i,len(jobDifficulty)):
                for k in range(j):
                    dp[i][j] = min(dp[i][j],dp[i-1][k]+max(jobDifficulty[k+1:j+1]))
        return dp[-1][-1]

class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        if d > len(jobDifficulty):
            return - 1
        
        last_day_max_efforts = [[float('inf')] * len(jobDifficulty) for _ in range(d)]
        
        last_day_max_efforts[0][0] = jobDifficulty[0]
        for i in range(1, len(jobDifficulty)):
            last_day_max_efforts[0][i] = max(last_day_max_efforts[0][i - 1], jobDifficulty[i])
        
        for day in range(1, d):
            for current_split in range(day, len(jobDifficulty)):
                for last_split in range(current_split):
                    last_day_max_efforts[day][current_split] = min(last_day_max_efforts[day][current_split], last_day_max_efforts[day - 1][last_split] + max(jobDifficulty[last_split + 1:current_split + 1]))
        
        return last_day_max_efforts[d - 1][len(jobDifficulty) - 1]

class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        jobs = jobDifficulty
        
        if len(jobs) < d:
            return -1
        
        return self.topDown(jobs, d, 0, {})
    
    def topDown(self, jobs, d, index, memo):
        if d <= 0:
            return float('inf')
        # if len(jobs) - index + 1 < d:
        #     return float('inf')
        if d == 1:
            if index < len(jobs):
                return max(jobs[index: ])
            return float('inf')
        
        if (d, index) in memo:
            return memo[(d, index)]
        
        mindiff = float('inf')
        
        for i in range(index, len(jobs)):
            mindiff = min(mindiff, self.topDown(jobs, d - 1, i + 1, memo) + max(jobs[index : i + 1]))
        memo[(d, index)] = mindiff
        return mindiff


from queue import PriorityQueue
#[11, 111, 22,  222, 33,  333,44,444]
class Solution:
    def getminSum(self,jobDifficulty, d,memo,start,end ):
        #print (d,start,end)
        if (start,end,d) in memo:
            return memo[(start,end,d)]
        if d == 1:
            return max(jobDifficulty[start:end+1])
        if end-start + 1 == 1:
            return -1
        #one split
        minSum= -1
        for i in range(start+1,end+1):
            part1 = max(jobDifficulty[start:i])
            
            part2 = self.getminSum(jobDifficulty,d-1,memo,i,end)
            if part2 == -1:
                continue 
            if minSum == -1:
                minSum = part1 + part2
            else:
                minSum = min(minSum, part1+part2)
        
        memo[(start,end,d)] = minSum
        #print(d, memo)
        return minSum
        
    
    def minDifficulty(self, jobDifficulty, d) -> int:
        
        memo = {}
        start = 0
        end = len(jobDifficulty)-1
        result = self.getminSum(jobDifficulty, d,memo, start,end)
        print (memo)
        return result



class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        
        jobs = jobDifficulty
        
        if len(jobs) < d:
            return -1
        
        return self.topDown(jobs, d, 0, {})
    
    def topDown(self, jobs, d, index, memo):
        if d <= 0:
            return float('inf')
        # if len(jobs) - index + 1 < d:
        #     return float('inf')
        if d == 1:
            if index < len(jobs):
                return max(jobs[index: ])
            return float('inf')
        
        if (d, index) in memo:
            return memo[(d, index)]
        
        mindiff = float('inf')
        
        for i in range(index, len(jobs)):
            mindiff = min(mindiff, self.topDown(jobs, d - 1, i + 1, memo) + max(jobs[index : i + 1]))
        memo[(d, index)] = mindiff
        return mindiff


import numpy as np
class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        n = len(jobDifficulty)
        dp = np.zeros((n,d+1))
        if d>n:
            return -1
        
        def rdp(i,j):
            if dp[i,j]==0:
                if j <= n-i:
                    if j==1:
                            dp[i,j] = max(jobDifficulty[i:])
                    else:
                            dp[i,j] = min([max(jobDifficulty[i:k])+rdp(k,j-1) for k in range(i+1,n)])
                else:
                    dp[i,j] = float('inf')

            return dp[i,j]

        return  int(rdp(0,d))     
                    


import numpy as np
class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        n = len(jobDifficulty)
        dp = np.zeros((n,d+1))
        if d>n:
            return -1
        
        def rdp(i,j):
            if dp[i,j]==0:
                if j <= n-i:
                    if j==1:
                            dp[i,j] = max(jobDifficulty[i:])
                    else:
                            dp[i,j] = min([max(jobDifficulty[i:k])+rdp(k,j-1) for k in range(i+1,n)])
                else:
                    dp[i,j] = float('inf')
            
            return dp[i,j]

        return  int(rdp(0,d))  


class Solution:
    def minDifficulty(self, jobs: List[int], d: int) -> int:
        if d>len(jobs):
            return -1
        elif d==len(jobs):
            summ=0
            for x in jobs:
                summ+=x
            return summ
        else:
            return self.topDown(jobs, d, 0, {})
    
    def topDown(self, jobs, d, index, memo):
        if d <= 0:
            return float('inf')
        # if len(jobs) - index + 1 < d:
        #     return float('inf')
        if d == 1:
            if index < len(jobs):
                return max(jobs[index: ])
            return float('inf')
        
        if (d, index) in memo:
            return memo[(d, index)]
        
        mindiff = float('inf')
        
        for i in range(index, len(jobs)):
            mindiff = min(mindiff, self.topDown(jobs, d - 1, i + 1, memo) + max(jobs[index : i + 1]))
        memo[(d, index)] = mindiff
        return mindiff

class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        
        from functools import lru_cache
        @lru_cache(None)
        def helper(jobs, d):
            if d==1:
                return max(jobs)
            mn=float('inf')
            for i in range(1, len(jobs)-d+2):
                s = max(jobs[:i])+helper(jobs[i:],d-1)
                mn = min(s, mn)
            return mn
        res = helper(tuple(jobDifficulty), d)
        return res if res!=float('inf') else -1
                


class Solution:
    def minDifficulty( self, jobDifficulty: List[ int ], d: int ) -> int:
        num_jobs = len( jobDifficulty )
        if num_jobs < d:
            return -1
        
        # The dp cache only keeps the best value up to that point for that number of days
        # This can be further optimized to only need two arrays since we only look at the previous row
        dp = [ [ -1 for _ in range( num_jobs ) ] for _ in range( d ) ]
        
        # First day everything is just the max up to that point
        max_so_far = -math.inf
        for job in range( num_jobs ):
            max_so_far = max( max_so_far, jobDifficulty[ job ] )
            dp[ 0 ][ job ] = max_so_far
        
        # Now do the rest
        for day in range( 1, d ):
            # In order to determine best difficulty, keep monotonic decreasing stack of difficulties
            # This will retain useful information up to each value and remove the need to loop backwards
            stack = []
            for job in range( day, num_jobs ): # Must be at least as many days as jobs
                # This value on its own plus the best of the previous
                dp[ day ][ job ] = dp[ day - 1 ][ job - 1 ] + jobDifficulty[ job ]
                # Keep stack in decreasing order
                while stack and jobDifficulty[ stack[ -1 ] ] <= jobDifficulty[ job ]:
                    index = stack.pop() 
                    dp[ day ][ job ] = min( dp[ day ][ job ], dp[ day ][ index ] - jobDifficulty[ index ] + jobDifficulty[ job ] )
                if stack:
                    dp[ day ][ job ] = min( dp[ day ][ job ], dp[ day ][ stack[ -1 ] ])
                
                stack.append( job )

        return dp[ -1 ][ -1 ]
        


class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        N = len(jobDifficulty)
        if d > N: return -1
        memo = [[float('inf')] * (d + 1) for _ in range(N + 1)]
        memo[0][0] = 0
        for i in range(1, N + 1):
            for k in range(1, min(i, d) + 1):
                memo[i][k] = min(memo[j][k - 1] + max(jobDifficulty[j:i]) for j in range(i - 1, -1, -1))
        return memo[N][d]

class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        size = len(jobDifficulty)
        memoi = [jobDifficulty[0]] * size
        for i in range(1, size):
            memoi[i] = max(memoi[i-1], jobDifficulty[i])
        maxes = {(0, i): memoi[i-1] for i in range(1, size + 1)}
        findMax = lambda s, e: maxes.setdefault((s, e), max(jobDifficulty[s:e]))
        for cut in range(1, d):
            newMemoi = [float('inf')] * size
            for end in range(cut, size):
                for split in range(cut - 1, end):
                    newMemoi[end] = min(
                        newMemoi[end],
                        memoi[split] + findMax(split+1, end+1)
                    )
            memoi = newMemoi
        return memoi[-1] if memoi[-1] != float('inf') else -1


class Solution:
    def minDifficulty(self, jobs: List[int], d: int) -> int:
        if len(jobs) < d:
            return -1
        
        return self.topDown(jobs, d, 0, {})
    
    def topDown(self, jobs, d, index, memo):
        
        if d <= 0:
            return float('inf')
        
        if len(jobs) - index + 1 < d:
            return float('inf')
        if d == 1:
            if index < len(jobs):
                return max(jobs[index: ])
            return float('inf')
        if (d, index) in memo:
            return memo[(d, index)]
        
        mindiff = float('inf')
        
        for i in range(index, len(jobs)):
            mindiff = min(mindiff, self.topDown(jobs, d - 1, i + 1, memo) + max(jobs[index : i + 1]))
        memo[(d, index)] = mindiff
        return mindiff


class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        def f(i,j, cache):
            if i==0:
                return 0 if j<0 else float('inf')
            if j<0: return float('inf')
            m=float('inf')
            if (i,j) in cache: return cache[(i,j)]
            for k in range(j+1):
                today=max(jobDifficulty[k:j+1])
                rest=f(i-1,k-1, cache)
                total=today+rest
                m=min(m, total)
            #print(i,j,m)
            cache[(i,j)] = m
            return m
        sol=f(d, len(jobDifficulty)-1, {})
        return -1 if sol==float('inf') else sol

class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        MAX = 300 * 1000 * 10
        N = len(jobDifficulty)
        cache = {}
        def dp(left_days: int, left_jobs_i: int, current_jobs_i: int) -> int:
            key = (left_days, left_jobs_i, current_jobs_i)
            if key not in cache:
                if left_jobs_i == N:
                    assert left_days > 0
                    if left_days == 1 and current_jobs_i < left_jobs_i:
                        cost = max(jobDifficulty[current_jobs_i:left_jobs_i])
                    else:
                        cost = MAX
                else:
                    cost = dp(left_days, left_jobs_i + 1, current_jobs_i)
                    if left_days > 1:
                        cost = min(cost, dp(left_days - 1, left_jobs_i + 1, left_jobs_i + 1) + max(jobDifficulty[current_jobs_i:(left_jobs_i + 1)]))
                cache[key] = cost
            return cache[key]
        ret = dp(d, 0, 0)
        if ret >= MAX:
            return -1
        return ret

class Solution:
    def minDifficulty(self, job_dif, d: int) -> int:
        len_job = len(job_dif)
        if d > len_job: return -1
        len_job += 1
        dp = [[float('inf')] * (d + 1) for _ in range(len_job)]
        job_dif = [0] + job_dif
        dp[0][0] = 0
        
        for i in range(1, len_job):
            for k in range(1, min(i+1, d+1)):
                for j in range(k, i+1):
                    dp[i][k] = min(dp[i][k], dp[j-1][k-1] + max(job_dif[j:i+1]))
        return dp[-1][-1]

class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        n = len(jobDifficulty)
        dp = [[float('inf')]*(d+1) for _ in range(n+1)]
        dp[0][0] = 0
        
        for i in range(1,n+1):
            for j in range(1,d+1):
                for h in range(j-1,i):
                    dp[i][j] = min(dp[i][j],dp[h][j-1] + max(jobDifficulty[h:i]) )
        return dp[n][d] if dp[n][d]!=float('inf') else -1


import sys

class Solution:
    def minDifficulty(self, complexity: List[int], days: int) -> int:
        if not complexity:
           return 0
        if len(complexity) < days:
           return -1
        m = days
        n = len(complexity)
        dp = [[sys.maxsize] * (n) for _ in range(m)]

        cur_max = complexity[0]
        for j in range(n):
           cur_max = max(complexity[j], cur_max)
           dp[0][j] = cur_max

        for i in range(1, m):
           for j in range(0, n):
               for k in range(0, j):
                   cur_max = max(complexity[k+1: j+1])
                   dp[i][j] = min(dp[i][j], dp[i-1][k] + cur_max)

        # print(dp)
        return dp[-1][-1]




class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        if len(jobDifficulty)<d: return -1
        @lru_cache(None)
        def dfs(i,d):
            if d==1: return(max(jobDifficulty[i:]))
            maxd, res = 0, float('inf')
            for j in range(i,len(jobDifficulty)-d+1):
                maxd = max(maxd, jobDifficulty[j])
                res =  min(res,maxd+dfs(j+1,d-1))
            return res
        return dfs(0,d)

class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        N = len(jobDifficulty)
        if d > N: return -1
        memo = [[float('inf')] * (d + 1) for _ in range(N + 1)]
        memo[0][0] = 0
        for i in range(1, N + 1):
            for k in range(1, min(i, d) + 1):
                memo[i][k] = min(memo[j][k - 1] + max(jobDifficulty[j:i]) for j in range(i - 1, -1, -1))
                # maxD = 0
                # :
                #     maxD = max(maxD, jobDifficulty[j])
                #     memo[i][k] = min(memo[i][k], memo[j][k - 1] + maxD)
        return memo[N][d]

class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        N = len(jobDifficulty)
        if N<d: return -1
        dp = [[float('inf')]*(N+1) for _ in range(d+1)]
        dp[0][0] = 0
        for i in range(1, d+1):
            for j in range(i, N+1):
                for k in range(i-1, j):
                    dp[i][j] = min(dp[i][j], dp[i-1][k]+max(jobDifficulty[k:j]))
                    
        return dp[-1][-1] if dp[-1][-1] != float('inf') else -1

class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        n = len(jobDifficulty)
        if d > n:
            return -1
        elif d == n:
            return sum(jobDifficulty)
        else:            
            '''
                1. can only do job i if job[0] ~ job[i-1] are done
                2. if cur job is t(i), we can put t(i+1) ~ t(j - 1) into the same day while t(i + 1) ~ t(j - 1) are all smaller than t(i)
                3. if t(j) >= t(i), then we must make a choice
                4. should we start from the end of the jobs? 
                    -> should be the same
                5. this should be a knapsack problem. 
                    -> for each day and each task, should we do it in the cur day? or the next day?                
                    -> and there will be the same node -> need memo
                    -> can we do bottom up?
                    
                6. 
                    dateIndex = 0 ~ (d - 1)
                    jobStartIndex = 0 ~ (n - 1)           
                    
                    dp[i][j]: the min cost at day i, job j                    
                    dp[i][j] = min(today's cost + future cost)
                                = min( 
                                        only do job-j: 
                                            jobDifficulty[j] + dp[i + 1][j + 1]
                                        do job-j, job-j + 1:
                                            max(jobDifficulty[j], jobDifficulty[j + 1]) + dp[i + 1][j + 2]                                        
                                        ...
                                        
                                        do max(jobDifficulty[j],..., jobDifficulty[n - 1]) + dp[i + 1][n]                                        
                                        )
                    so we need to do i + 1 first and j + 1 first            
            '''
            n = len(jobDifficulty)
            dp = dict()
            for d in range(0, d + 1):
                dp[d] = dict()                     
                for j in range(0, n + 1):
                    dp[d][j] = float('inf')
            
            dp[d][n] = 0
                            
            for i in range(d - 1, -1, -1):                                                           
                for j in range(n - 1, i - 1, -1):                    
                    for k in range(j, n): #do job j ~ k, k = j ~ n - 1, so the next day start from job k + 1
                        futureCost = dp[i + 1][k + 1]
                        todayCost = max(jobDifficulty[j:k + 1])                                       
                        #print([i, j, k])                                                                                                   
                        dp[i][j] = min(dp[i][j], todayCost + futureCost)                    
                                                                    
            return dp[0][0]
                    


class Solution:
    def minDifficulty(self, jobs: List[int], d: int) -> int:
        if d > len(jobs):
            return -1
        memo = {}
        return self.findjob(jobs, d, 0, memo)
    def findjob(self, jobs, d, index, memo):
        if d <= 0:
            return float('inf')
        if d == 1:
            if index < len(jobs):
                return max(jobs[index: ])
            return float('inf')

        if (d, index) in memo:
            return memo[(d, index)]

        mini = float('inf')
        for i in range(index, len(jobs)):
            mini = min(mini, self.findjob(jobs, d-1, i+1, memo) + max(jobs[index : i+1]))
        memo[(d, index)]  = mini
        return mini


class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        N = len(jobDifficulty)
        dp = [[float('inf')]*(N+1) for _ in range(d+1)]
        dp[0][0] = 0
        for i in range(1, d+1):
            for j in range(i, N+1):
                for k in range(i-1, j):
                    dp[i][j] = min(dp[i][j], dp[i-1][k]+max(jobDifficulty[k:j]))
                    
        return dp[-1][-1] if dp[-1][-1] != float('inf') else -1

class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        n = len(jobDifficulty)
        if d > n:
            return -1
        dp = [[float('inf') for col in range(d+1)] for row in range(n+1)]
        dp[0][0] = 0
        for i in range(1, 1+n):
            for k in range(1, 1+d):
                for j in range(i, k-1, -1):
                    dp[i][k] = min(dp[i][k], dp[j-1][k-1]+max(jobDifficulty[j-1:i]))
        return dp[-1][-1]

class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        n = len(jobDifficulty)
        if d > n: return -1
        dp = [[float('inf') for _ in range(d+1)] for _ in range(n+1)]
        dp[0][0] = 0
        for i in range(1, n+1):  # number of jobs, convert to index is i-1
            for k in range(1, d+1):   # number of days
                for j in range(i-1, k-2, -1): # j is job index: i-1 -> k-1
                    dp[i][k] = min(dp[i][k], dp[j][k-1]+max(jobDifficulty[j:i]))
                    #前j个job, k-1天 + i-j个job的max
        return dp[-1][-1]


from functools import lru_cache


class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        
        n = len(jobDifficulty)
        if n < d:
            return -1

        @lru_cache(None)        
        def helper(i, d):
            nonlocal jobDifficulty, n
            
            if i >= n and d != 0:
                return float('inf')
            if d == 1:
                return max(jobDifficulty[i:])
            
            
            max_till_now = float('-inf')
            ans = float('inf')

            for j in range(i, n - d + 1):
                max_till_now = max(max_till_now, jobDifficulty[j])
                ans = min(ans, max_till_now + helper(j + 1, d - 1))
            return ans
        
        return helper(0, d)

class Solution:
    def minDifficulty(self, jobsd: List[int], d: int) -> int:
        @lru_cache(maxsize=None)
        def cut(st, days):
            if st == len(jobsd) or days == 0 or len(jobsd) - st < days:
                return math.inf
            if days == 1:
                return max(jobsd[st:])
            maxsofar, res = -math.inf, math.inf
            for i in range(st, len(jobsd)-1):
                maxsofar = max(maxsofar, jobsd[i])
                res = min(res, maxsofar + cut(i+1, days-1))
            return res
        res = cut(0, d)
        return -1 if res == math.inf else res


class Solution:
    def minDifficulty(self, jobsd: List[int], d: int) -> int:
        @lru_cache(maxsize=None)
        def cut(st, days):
            if st == len(jobsd) or days == 0 or len(jobsd) - st < days:
                return math.inf
            if days == 1:
                return max(jobsd[st:])
            maxsofar, res = -math.inf, math.inf
            for i in range(st, len(jobsd)-1):
                maxsofar = max(maxsofar, jobsd[i])
                res = min(res, maxsofar + cut(i+1, days-1))
            return res
        res = cut(0, d)
        return -1 if res == math.inf else res
                


import functools
class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        n = len(jobDifficulty)
        if n < d: return -1

        @functools.lru_cache(None)
        def dfs(i, d):
            if d == 1:
                return max(jobDifficulty[i:])
            res, maxd = float('inf'), 0
            for j in range(i, n - d + 1):
                maxd = max(maxd, jobDifficulty[j])
                res = min(res, maxd + dfs(j + 1, d - 1))
            return res
        return dfs(0, d)

class Solution:

    def minDifficulty(self, jobsd: List[int], d: int) -> int:
        @lru_cache(maxsize=None)
        def cut(st, days):
            if st == len(jobsd) or days == 0 or len(jobsd) - st < days:
                return math.inf
            if days == 1:
                return max(jobsd[st:])
            maxsofar, res = -math.inf, math.inf
            for i in range(st, len(jobsd)-1):
                maxsofar = max(maxsofar, jobsd[i])
                res = min(res, maxsofar + cut(i+1, days-1))
            return res
        res = cut(0, d)
        return -1 if res == math.inf else res


import functools
class Solution:

    def minDifficulty(self, A, d):
        n = len(A)
        if n < d: return -1

        @functools.lru_cache(None)
        def dfs(i, d):
            if d == 1:
                return max(A[i:])
            res, maxd = float('inf'), 0
            for j in range(i, n - d + 1):
                maxd = max(maxd, A[j])
                res = min(res, maxd + dfs(j + 1, d - 1))
            return res
        return dfs(0, d)

class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        N = len(jobDifficulty)
        dp = [0]+[float('inf')]*N
        
        for i in range(1, d+1):
            dp2 = [float('inf')]*(N+1)
            
            stack = []
            # print(\"\")
            for j in range(i, N+1-d+i):
                # print(\"i:\", i, \"dp2:\", dp2, \", stack:\", stack)
                curr_max = jobDifficulty[j-1]
                if i==1:
                    dp2[j] = max(jobDifficulty[:j])
                else:
                    dp2[j] = dp[j-1]+curr_max
                    
                while stack and stack[-1][1]<=curr_max:
                    dp2[j] = min(dp2[j], dp2[stack[-1][0]]-stack[-1][1]+curr_max)
                    stack.pop()
                    
                if stack and dp2[stack[-1][0]]<dp2[j]:
                    dp2[j] = dp2[stack[-1][0]]
                    curr_max = stack[-1][1]
                
                stack.append((j, curr_max))
            dp = dp2
        return dp[N] if dp[N]!=float('inf') else -1    


class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        
        from functools import lru_cache
        @lru_cache(None)
        def helper(st, d):
            if st == len(jobDifficulty) or d == 0 or len(jobDifficulty) - st < d:
                return math.inf
            if d==1:
                return max(jobDifficulty[st:])
            mn, mx=float('inf'), float('-inf')
            for i in range(st+1, len(jobDifficulty)-d+2):
                mx = max(mx, jobDifficulty[i-1])
                s = mx+helper(i,d-1)
                mn = min(s, mn)
            return mn
        res = helper(0, d)
        return res if res!=float('inf') else -1
                


class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        # @lru_cache(None)
        # def helper(start, d):
        #     if len(jobDifficulty) - start < d:
        #         return float('inf')
        #     if d == 1:
        #         return max(jobDifficulty[start:])
        #     result = float('inf')
        #     for i in range(start, len(jobDifficulty) - d + 1):
        #         result = min(result, max(jobDifficulty[start:i+1]) + helper(i+1, d-1))
        #     return result
        # result = helper(0, d)
        # return result if result != float('inf') else -1
        if len(jobDifficulty) < d:
            return -1
        dp = [[float('inf')] * (d + 1) for _ in range(len(jobDifficulty))]
        tempmax = 0
        for i, job in enumerate(jobDifficulty):
            tempmax = max(tempmax, job)
            dp[i][1] = tempmax
        for day in range(2, d+1):
            for j in range(day-1, len(jobDifficulty)):
                result = float('inf')
                tempmax = 0
                for k in range(j, day-3, -1):
                    tempmax =  max(tempmax, jobDifficulty[k])
                    result = min(result, dp[k-1][day-1] + tempmax)
                dp[j][day] = result
        # print(dp)
        return dp[-1][-1]


class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        n = len(jobDifficulty)
        if d > n:
            return -1
        difficulties = [[0] * n for _ in range(n)]
        for i in range(n):
            difficulties[i][i] = jobDifficulty[i]
            for j in range(i+1,n):
                difficulties[i][j] = max(difficulties[i][j - 1], jobDifficulty[j])
        #print(difficulties)
        dp = [[float('inf')] * (d + 1) for _ in range(n)]
        for i in range(n):
            dp[i][1] = difficulties[0][i]
            for p in range(2, d + 1):
                for j in range(i):
                    dp[i][p] = min(dp[i][p], dp[j][p - 1] + difficulties[j+1][i])
        #print(dp)
        return dp[n - 1][d]

class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        memo= {}
        n = len(jobDifficulty)
        for i in range(n):
            for j in range(i,n):
                if i==j:
                    memo[(i,j)]=jobDifficulty[i]
                else:
                    memo[(i,j)]=max(memo[(i,j-1)],jobDifficulty[j])
        if n<d:
            return -1
        @lru_cache(None)
        def dfs(i,d):
            
            if d == 1:
                return memo[(i,n-1)]
            res = float('inf')
            for j in range(i, n - d + 1):
                res = min(res, memo[(i,j)]+ dfs(j + 1, d - 1))
            return res
        return dfs(0,d)
                    


from functools import lru_cache

class Solution:
  @lru_cache(None)
  def recursive(self, i, k):
    if k == 1:
      return max(self.x[i:])
    m, ans = self.x[i], float('inf')
    for j in range(i + 1, self.n + 2 - k):
      ans = min(ans, m + self.recursive(j, k - 1))
      m = max(m, self.x[j])
    return ans
  def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
    # split the array into d subarray, want to minimize sum(max(subarrays))
    self.x, self.n = jobDifficulty, len(jobDifficulty)
    if self.n < d:
      return -1
    self.recursive.cache_clear()
    return self.recursive(0, d)

class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        if len(jobDifficulty) < d:
            return -1
        elif len(jobDifficulty) == d:
            return sum(jobDifficulty)
        
        matrix = [[0] * len(jobDifficulty) for i in range(len(jobDifficulty))]
        
        for i in range(1,len(jobDifficulty)+1):
            for j in range(len(jobDifficulty)):
                if i+j-1 >= len(jobDifficulty):
                    continue
                matrix[j][i+j-1] = max(jobDifficulty[i+j-1],matrix[j][i+j-2] if i >1 else 0)
        
        dp=[[float('inf')]*(len(jobDifficulty)+1) for i in range(d+1)]
        
        for i in range(1,d+1):
            for j in range(1,len(jobDifficulty)+1):
                if i==1:
                    dp[i][j]=matrix[0][j-1]
                elif j>1:
                    dp[i][j]=min([dp[i-1][j-k]+matrix[j-k+1-1][j-1] for k in range(1,j)])
                    
        return dp[-1][-1]

class Solution:
    def _tmp(self):
        jd = jobDifficulty
        inf = 1e9
        l = len(jd)
        
        if l < d:
            return -1
        
        @functools.lru_cache(None)
        def dfs(i, d):
            if d == 1:
                return max(jd[i:])
            mind = inf
            maxd = 0
            for j in range(i, l - d + 1):
                maxd = max(maxd, jd[j])
                mind = min(mind, maxd + dfs(j + 1, d - 1))
            return mind
        
        return dfs(0, d)
    
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        jd = jobDifficulty
        inf = 1e9
        l = len(jd)
        if l < d:
            return -1
        opt = [[0] * (l - d_) + [inf] * (d_) for d_ in range(d)]
        
        #for r in opt:
        #    print(r)
        #print()
        
        for i in range(d):
            for j in range(l - i):
                if i == 0:
                    opt[i][j] = max(jd[j:])
                    continue
                maxc = 0
                mino = inf
                for k in range(j, l - i):
                    maxc = max(maxc, jd[k])
                    mino = min(mino, maxc + opt[i - 1][k + 1])
                opt[i][j] = mino
        
        #for r in opt:
        #    print(r)
        
        return opt[d - 1][0]


class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        m=len(jobDifficulty)
        if m == 0 or d == 0 or d > m:
            return -1
        fmax = [[0]*m for _ in range(m)]    #fmax[i][j]: max of [i ~ j], inclusive index
        fdm = [[None]*m for _ in range(d+1)]    #fdm[di][mi]: di days end on mi_th job, fdm[1][mi] means day one finish on mi_th job 
        for i in range(m):
            for delta in range(m-i):
                if delta == 0:
                    fmax[i][i+delta] = jobDifficulty[i]
                else:
                    fmax[i][i+delta] = max(fmax[i][i+delta-1], jobDifficulty[i+delta])
        
        for mi in range(m):
            fdm[1][mi] = fmax[0][mi]    #fdm[1][mi] means day one finish on mi_th job , so it's the max from [0 ~ mi]
        
        for di in range(2, d+1):  #deduce next possible minimal, and find fmd(d, m) finally, 
            for mi in range(di-1, m-d+di):
                for ki in range(di-2, mi):
                    if not fdm[di][mi]:
                        fdm[di][mi] = fdm[di-1][ki] + fmax[ki+1][mi]
                    else:
                        fdm[di][mi] = min(fdm[di][mi], fdm[di-1][ki] + fmax[ki+1][mi])    # ki range in [di-2 ~ mi)


        return fdm[d][m-1]


class Solution:
    def minDifficulty(self, A: List[int], d: int) -> int:
        n = len(A)
        dp, dp2 = [float('inf')] * n, [0] * n
        if n < d: return -1
        for d in range(d):
            stack = []
            for i in range(d, n):
                dp2[i] = dp[i - 1] + A[i] if i else A[i]
                while stack and A[stack[-1]] <= A[i]:
                    j = stack.pop()
                    dp2[i] = min(dp2[i], dp2[j] - A[j] + A[i])
                if stack:
                    dp2[i] = min(dp2[i], dp2[stack[-1]])
                stack.append(i)
            dp, dp2 = dp2, [0] * n
        return dp[-1]

class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        
        if not jobDifficulty or len(jobDifficulty)<d: return -1
        
        @lru_cache(None)
        def dp(start, rem):
            
            if rem==0:
                return 0 if start >= len(jobDifficulty) else math.inf
            if start >= len(jobDifficulty):
                return 0 if rem == 0 else math.inf
            
            maxDiff = -math.inf
            minDiff = math.inf
            
            for i in range(start, len(jobDifficulty)):
                maxDiff = max(maxDiff, jobDifficulty[i])
                minDiff = min(minDiff, maxDiff+dp(i+1, rem-1))
            
            return minDiff
        
        ans = dp(0, d)
        return ans if ans != math.inf else -1
        
        # [6,5,4,3,2,1] d=2


class Solution:
    def minDifficulty(self, jd: List[int], d: int) -> int:
        jd_len = len(jd)
        if d > jd_len: return -1
        
        hidp = [0] * jd_len  
        hidp[-1] = jd[-1]
        for i in range(jd_len - 2, -1, -1):
            hidp[i] = max(jd[i], hidp[i + 1])        
        
        dp = [{} for i in range(d)]
        
        def find_min(idx:int, _d:int) -> int:
            cache = dp[_d]
            if idx in cache: return cache[idx]
            
            score = float('inf')
            if _d == 0:
                score = hidp[idx]
            else:    
                hi = 0
                for i in range(idx, jd_len - _d):
                    hi = max(hi,jd[i])                     
                    score = min(score, hi + find_min(i+1,_d - 1))
            cache[idx] = score         
            return score
        res = find_min(0, d - 1)
        return res

class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        if len(jobDifficulty) < d:
            return -1
        
        @lru_cache(None)
        def dfs(index, d):
            if index == len(jobDifficulty) and d == 0:
                return 0
            
            if d == 0 and index < len(jobDifficulty):
                return float('inf')
            
            temp = float('inf')
            curr = 0
            for i in range(index, len(jobDifficulty)):
                curr = max(curr, jobDifficulty[i])
                temp = min(temp, curr + dfs(i + 1, d - 1))
            
            return temp
        
        return dfs(0, d)

class Solution:
    def minDifficulty(self, jd: List[int], d: int) -> int:
        n = len(jd)
        if n < d: return -1
        dp= [[0] * n for _ in range(d)]
        dp[0][0] = jd[0]
        for i in range(1, n):
            dp[0][i] = max(jd[i], dp[0][i-1])
        for i in range(1, d):
            for j in range(i, n):
                dp[i][j] = float('inf')
                curMax = jd[j]
                for r in range(j, i-1, -1):
                    curMax = max(curMax, jd[r])
                    dp[i][j] = min(dp[i][j], dp[i-1][r-1] + curMax)
    
        return dp[d-1][n-1]

class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        @lru_cache(maxsize=None)
        def helper(i, d):
            if d == 1:
                return max(jobDifficulty[i::])
            if len(jobDifficulty)-i < d or d == 0:
                return -1
            if len(jobDifficulty)-i == d:
                return sum(jobDifficulty[i::])
            tans = 2**64
            max_d = jobDifficulty[i]
            for j in range(0, len(jobDifficulty)-i-d+1):
                max_d = max(max_d, jobDifficulty[i+j])
                tans = min(helper(i+j+1, d-1)+max_d, tans)
            return tans                
        return helper(0, d)


class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        if d > len(jobDifficulty): return -1
        m = len(jobDifficulty)
        dp = [[float('inf') for _ in range(m)] for _ in range(d)]
        for i in range(0, d):
            if i == 0:
                val = jobDifficulty[0]
                for j in range(m - d + i + 1):
                    val = max(jobDifficulty[j], val)
                    dp[i][j] = val
            else:
                for j in range(i, m - d + i + 1):
                    val = jobDifficulty[j]
                    for k in range(j - 1, i - 2, -1):
                        val = max(jobDifficulty[k + 1], val)
                        dp[i][j] = min(dp[i][j], dp[i - 1][k] + val)
        # print(dp)
        return dp[-1][-1]


class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        n = len(jobDifficulty)
        grid = [[-1]*n for i in range(d)]
        M = sum(jobDifficulty)
        
        m = 0
        for i in reversed(range(len(grid[0]))):
            m = max(jobDifficulty[i], m)
            grid[0][i] = m
            
        for i in range(1, d):
            for j in reversed(range(len(grid[i-1]))):
                m = jobDifficulty[j]
                tmp = M
                got = False
                for k in range(j+1, len(grid[i-1])):
                    # print(i, j, k)
                    if grid[i-1][k] > -1:
                        tmp = min(m+grid[i-1][k], tmp)
                        got = True
                    m = max(jobDifficulty[k], m)
                if got:
                    grid[i][j] = tmp


                        
        # print(grid)
        
        return grid[-1][0]                

class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        N = len(jobDifficulty)
        if d > N: return -1
        memo = [[float('inf')] * (d + 1) for _ in range(N + 1)]
        memo[0][0] = 0
        for i in range(1, N + 1):
            maxD = 0
            for j in range(i - 1, -1, -1):
                maxD = max(maxD, jobDifficulty[j])
                for k in range(1, min(i, d) + 1):
                    memo[i][k] = min(memo[i][k], memo[j][k - 1] + maxD)
        return memo[N][d]

class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        N = len(jobDifficulty)
        dp = [0]+[float('inf')]*N
        
        for i in range(1, d+1):
            dp2 = [float('inf')]*(N+1)
            stack = []
            for j in range(i, N+1-d+i):
                curr_max = jobDifficulty[j-1]
                if i==1:
                    dp2[j] = max(jobDifficulty[:j])
                else:
                    dp2[j] = dp[j-1]+curr_max
                    
                while stack and stack[-1][1]<=curr_max:
                    dp2[j] = min(dp2[j], dp2[stack[-1][0]]-stack[-1][1]+curr_max)
                    stack.pop()
                    
                if stack and dp2[stack[-1][0]]<dp2[j]:
                    dp2[j] = dp2[stack[-1][0]]
                    curr_max = stack[-1][1]
                
                stack.append((j, curr_max))
            dp = dp2
        return dp[N] if dp[N]!=float('inf') else -1    


class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        if d > len(jobDifficulty):
            return -1
        
        dp = [[0] * (len(jobDifficulty)) for _ in range(d)]
        
        dp[0][0] = jobDifficulty[0]
        for i in range(1,len(jobDifficulty)):
            dp[0][i] = max(dp[0][i-1], jobDifficulty[i])

        for di in range(1, d):
            for j in range(di, len(jobDifficulty)):
                localMax = jobDifficulty[j];
                dp[di][j] = 10*1000 + 1;
                for r in range(j, di-1, -1):
                    localMax = max(localMax, jobDifficulty[r]);
                    dp[di][j] =  min(dp[di][j], dp[di-1][r-1] + localMax);
                #dp[di][j] = jobDifficulty[j - 1] + dp[di - 1][j-1]
        return dp[-1][-1]
    
    #int localMax = jobDifficulty[j];
    #            dp[i][j] = Integer.MAX_VALUE;
    #            for(int r = j; r >= i; r--){
    #                localMax = Math.max(localMax,jobDifficulty[r]);
    #                dp[i][j] =  Math.min(dp[i][j],dp[i-1][r-1] + localMax);
    #            }class Solution {
    #public int minDifficulty(int[] jobDifficulty, int d) {
        
#\t\tint n = jobDifficulty.length; 
 #       if(n < d) return -1;
#        int[][] dp = new int[d][n];
#        
#        dp[0][0] = jobDifficulty[0];
#        for(int i = 1; i < n; i++){
#            dp[0][i] = Math.max(jobDifficulty[i],dp[0][i-1]);
#        }
        
#        for(int i = 1; i < d; i++){
#            for(int j = i; j < n; j++){
#                int localMax = jobDifficulty[j];
#                dp[i][j] = Integer.MAX_VALUE;
#                for(int r = j; r >= i; r--){
#                    localMax = Math.max(localMax,jobDifficulty[r]);
#                    dp[i][j] =  Math.min(dp[i][j],dp[i-1][r-1] + localMax);
#                }
#            }
#        }
        
#        return dp[d-1][n-1];
#    }
#}


class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        A = jobDifficulty
        n, inf = len(A), float('inf')
        if n < d: return -1
        dp = [inf] * n + [0]
        for d in range(1, d + 1):
            for i in range(n - d + 1):
                maxd, dp[i] = 0, inf
                for j in range(i, n - d + 1):
                    maxd = max(maxd, A[j])
                    dp[i] = min(dp[i], maxd + dp[j + 1])
        return dp[0]

# 11:19 - 
class Solution:
    def minDifficulty(self, difficulty: List[int], d: int) -> int:
        # dp[n, d] = dp[n - 1, d - i] + max(n - i, n) 
        if d > len(difficulty):
            return -1
        
        n = len(difficulty)
        dp = [float('inf')] * n + [0]
        
        # dp[i, j]: finish 'j' jobs in 'i' days
        for i in range(d):
            for j in range(n - 1, i - 1, -1):
                dp[j] = float('inf')
                local = float('-inf')
                for k in range(j, i - 1, -1):
                    local = max(local, difficulty[k])
                    dp[j] = min(dp[j], dp[k - 1] + local)
        
        return dp[-2]


from functools import lru_cache


class Solution:
    def minDifficulty(self, A: List[int], d: int) -> int:
        if len(A) < d:
            return -1
        
        @lru_cache(None)
        def helper(i, d):
            if i == len(A):
                if d == 0:
                    return 0
                return float('inf')
            
            if d == 0:
                return float('inf')
            
            res = float('inf')
            local_max = float('-inf')
            for j in range(i, len(A)):
                local_max = max(local_max, A[j])
                res = min(res, local_max + helper(j + 1, d - 1))
            return res
        
        res = helper(0, d)
        return res if res < float('inf') else -1


class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        jD = jobDifficulty
        N = len(jD)
        if d > N:
            return -1
        
        dp = [[float('inf')] * N for _ in range(d)]
        dp[0][0] = jD[0]
        for j in range(1,N):
            dp[0][j] = 0
            dp[0][j] = max(dp[0][j-1], jD[j])
        # dp[i][j] = min(dp[i-1][k] + max(jD[k+1:j])) for k in i-1,j-1
        for i in range(1,d):
            for j in range(i, N):
                # print('i,j = ',i,j)
                last_dayD = jD[j]
                for k in range(j-1, i-2, -1):
                    # print('k = ',k)
                    last_dayD = max(last_dayD, jD[k+1])
                    # print('last_dayD = ',last_dayD)
                    dp[i][j] = min(dp[i][j], dp[i-1][k] + last_dayD)
        # print(dp)
        return dp[d-1][N-1]
    #[7,3,2,3,4,5]
    # 5


from functools import lru_cache

class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        n = len(jobDifficulty)
        @lru_cache(None)
        def dfs(idx, day):
            if day == 0:
                if idx < n:
                    return float('inf')
                else:
                    return 0
            tmp = 0
            res = float('inf')
            for j in range(idx, n):
                tmp = max(tmp, jobDifficulty[j])
                res = min(res, tmp + dfs(j + 1, day - 1))
            return res
        
        out = dfs(0, d)
        if out == float('inf'):
            return -1
        return out


class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        N = len(jobDifficulty)
        dp = [0]+[float('inf')]*N
        
        for i in range(1, d+1):
            dp2 = [float('inf')]*(N+1)
            stack = []
            for j in range(i, N+1-d+i):
                max_val = jobDifficulty[j-1]
                if i==1:
                    dp2[j] = max(jobDifficulty[:j])
                else:
                    dp2[j] = dp[j-1]+max_val
                    
                while stack and stack[-1][1]<=max_val:
                    dp2[j] = min(dp2[j], dp2[stack[-1][0]]-stack[-1][1]+max_val) 
                    stack.pop()
                    
                if stack and dp2[stack[-1][0]]<dp2[j]:
                    dp2[j] = dp2[stack[-1][0]]
                    max_val = stack[-1][1]
                
                stack.append((j, max_val))
            # print(i, dp2)
            dp = dp2
            
        return dp[N] if dp[N]!=float('inf') else -1

class Solution:
    def minDifficulty(self, arr: List[int], d: int) -> int:
        n = len(arr)
        if d==1: return max(arr)
        if d>n: return -1
        if d==n: return sum(arr)
        dp = [[float('inf') for _ in range(n)] for _ in range(d)]
        #initialization
        dp[0][0] = arr[0]
        for i in range(1,n):
            dp[0][i] = max(dp[0][i-1], arr[i])
        for i in range(1,d):
            for j in range(i, n):
                diff = 0
                for k in range(j, i-1, -1):
                    diff = max(arr[k], diff)
                    dp[i][j] = min(dp[i][j], dp[i-1][k-1] + diff)
        return dp[d-1][n-1]

import functools
class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        n, inf = len(jobDifficulty), float('inf')
        if n < d:
            return -1
        dp = [inf]* n + [0]
        for day in range(1, d + 1):
            for i in range(n - day + 1):
                maxd, dp[i] = 0, inf
                for j in range(i, n - day + 1):
                    maxd = max(maxd, jobDifficulty[j])
                    dp[i] = min(dp[i], maxd + dp[j+1])
        return dp[0]

import sys

class Solution:
    def minDifficulty(self, complexity: List[int], days: int) -> int:
       num_tasks = len(complexity)
       if num_tasks < days:
           return -1
       dp = [sys.maxsize] * (num_tasks + 1)
       dp[0] = 0

       for day in range(1, days+1):
           for i in range(num_tasks, 0, -1):
               cur_max = 0
               dp[i] = sys.maxsize if i > day-1 else dp[i]
               for k in range(i, day-1, -1):
                   cur_max = max(cur_max, complexity[k-1])
                   dp[i] = min(dp[i], dp[k-1] + cur_max)
       print(dp)
       return dp[-1]





class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        n = len(jobDifficulty)
        if n < d:
            return -1
        dp = [[0] * n] + [[float('inf')] * n for _ in range(d - 1)]
        dp[0][0] = jobDifficulty[0]
        for i in range(1, n):
            dp[0][i] = max(jobDifficulty[i], dp[0][i - 1])
        for i in range(1, d):
            for j in range(i, n):
                max_r = jobDifficulty[j]
                for r in range(j, i - 1, -1):
                    max_r = max(max_r, jobDifficulty[r])
                    dp[i][j] = min(dp[i][j], max_r + dp[i - 1][r - 1])
        return dp[-1][-1]

class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        if len(jobDifficulty)<d:
            return -1
        
        #dp[i][j]表示第i天以第j个任务结尾，总的最小的difficulty
        dp=[ [float('inf')]*len(jobDifficulty) for _ in range(d) ] 
        
        dp[0][0]=jobDifficulty[0]
        for j in range(1,len(jobDifficulty)):
            dp[0][j]=max(dp[0][j-1],jobDifficulty[j])
        
        for i in range(1,d):
            for j in range(i,len(jobDifficulty)):
                maxdif=0
                for k in range(j-1,-1,-1):
                    maxdif=max(maxdif,jobDifficulty[k+1])
                    dp[i][j]=min(dp[i][j],dp[i-1][k]+maxdif)

        
        return dp[-1][-1]


class Solution:
    def minDifficulty(self, A: List[int], d: int) -> int:
        n = len(A)
        if(n<d):
            return -1
        
        @lru_cache(None)
        def helper(i,d):
            if(d == 0):
                return 0 if i == n else sum(A[i:])
            
            if(i == n):
                return float('inf')
            tmp = 0
            ans = float('inf')
            for j in range(i,n):
                tmp = max(tmp,A[j])
                ans = min(ans, tmp + helper(j+1,d-1))
            return ans
        return helper(0,d)

class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        n = len(jobDifficulty)
        M = 1e6
        dp = [M for i in range(n + 1)]
        dp[n] = 0
        for j in range(1, d + 1):
            for i in range(n):
                m = -1
                dp[i] = M
                for k in range(i, n):
                    m = max(m, jobDifficulty[k])
                    dp[i] = min(dp[i], m + dp[k + 1])
            dp[n] = M
        return dp[0] if dp[0] < M else -1


class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        N = len(jobDifficulty)
        cache = {}
        def dfs(start, days):
            if (start, days) in cache:
                return cache[(start, days)]
            if N - start < days or start == N or days < 1:
                cache[(start, days)] = -1
            elif days == 1:
                cache[(start, days)] = max(jobDifficulty[start:])
            else:
                max_daily = float('-inf')
                min_all = float('inf')
                for end in range(start, N-days+1):
                    max_daily = max(max_daily, jobDifficulty[end])
                    min_all = min(min_all, max_daily + dfs(end+1, days-1))
                cache[(start, days)] = -1 if min_all == float('inf') else min_all
            return cache[(start, days)]
        
        return dfs(0, d)


class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        
        n = len(jobDifficulty)
        if n < d: return -1
        memo = {}
        def dp(ii, day):            
            if (ii, day) not in memo:
                if n - ii == day: memo[(ii, day)] = sum(jobDifficulty[ii:])
                elif day == 1: memo[(ii, day)] = max(jobDifficulty[ii:])
                else:
                    ans = float('inf')
                    curr_max = float('-inf')
                    for jj in range(ii, n-(day-1)):
                        #print(jj, day)
                        curr_max = max(curr_max, jobDifficulty[jj])
                        ans =min(ans, curr_max+dp(jj+1, day-1))
                    
                    memo[(ii, day)] = ans
            return memo[(ii, day)]
        
        ans = dp(0, d)
        #print(memo)
        return ans

class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        N = len(jobDifficulty)
        memo = {}
        def helper(start, days):
            if (start, days) in memo:
                return memo[(start,days)]
            if start == N or days < 1 or N - start < days: 
                memo[(start, days)] = -1
            elif days == 1:
                memo[(start, days)] = max(jobDifficulty[start:])
            else:
                max_diff = float('-inf')
                min_total = float('inf')
                for i in range(start, N-days+1):
                    max_diff = max(max_diff, jobDifficulty[i])
                    min_total = min(min_total, max_diff + helper(i+1, days-1))
                memo[(start, days)] = -1 if min_total == float('inf') else min_total
            return memo[(start, days)]
        return helper(0, d)

class Solution:
    def minDifficulty( self, jobDifficulty: List[ int ], d: int ) -> int:
        num_jobs = len( jobDifficulty )
        if num_jobs < d:
            return -1
        
        dp = [ [ -1 for _ in range( num_jobs ) ] for _ in range( d ) ]
        
        # First day everything is just the max up to that point
        max_so_far = -math.inf
        for job in range( num_jobs ):
            max_so_far = max( max_so_far, jobDifficulty[ job ] )
            dp[ 0 ][ job ] = max_so_far
        
        # Now do the rest
        for day in range( 1, d ):
            for job in range( day, num_jobs ): # Must be at least as many days as jobs
                # The dp cache only keeps the best value up to that point for that number of days
                # In order to determine best difficulty, walk backwards while keeping track of max difficulty and determine min total effort
                max_so_far = -math.inf
                for backwards_walker in range( job, day - 1, -1 ):
                    max_so_far = max( max_so_far, jobDifficulty[ backwards_walker ] )
                    dp[ day ][ job ] = min( dp[ day ][ job ], max_so_far + dp[ day - 1 ][ backwards_walker - 1 ] ) if dp[ day ][ job ] != -1 else max_so_far + dp[ day - 1 ][ job - 1 ]
        print( dp )
        return dp[ -1 ][ -1 ]


import sys

class Solution:
    def minDifficulty(self, complexity: List[int], days: int) -> int:
        n = len(complexity)
        if n < days:
            return -1
        dp = [[sys.maxsize] * (days + 1) for _ in range(n + 1)]
        dp[0][0] = 0
        for i in range(1, n+1):
            for j in range(1, days+1):
                cur_max = 0
                for k in range(i - 1, j - 2, -1):
                    cur_max = max(cur_max, complexity[k])
                    dp[i][j] = min(dp[i][j], dp[k][j-1] + cur_max)
        return dp[-1][-1]


class Solution:
    def minDifficulty(self, A, d):
        n, inf = len(A), float('inf')
        dp = [[inf] * n + [0] for i in range(d + 1)]
        for d in range(1, d + 1):
            for i in range(n - d + 1):
                maxd = 0
                for j in range(i, n - d + 1):
                    maxd = max(maxd, A[j])
                    dp[d][i] = min(dp[d][i], maxd + dp[d - 1][j + 1])
        return dp[d][0] if dp[d][0] < inf else -1

class Solution:
    def minDifficulty(self, A: List[int], d: int) -> int:
        n = len(A)
        
        if d>n: #more days than job
            return -1
        
        dp = [[math.inf]*(d+1) for _ in range(n)]
        #dp[i][j] store the ans for jobs i:n with j days remaining
        
        for i in range(n-1,-1,-1):
            for j in range(1,d+1):
                if n-i<j: #more days than jobs
                    continue
                rMax = -math.inf
                for k in range(i,n-j+1): #if we finish i:k+1 jobs today
                    rMax=max(rMax,A[k])
                    if j==1:
                        dp[i][j]=rMax
                    else:
                        dp[i][j] = min(dp[i][j],rMax+dp[k+1][j-1])
        return dp[0][d]


class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        A = jobDifficulty
        n = len(A)
        
        if d>n: #more days than job
            return -1
        
        dp = [[math.inf]*(d+1) for _ in range(n)]
        #dp[i][j] store the ans for jobs i:n with j days remaining
        
        for i in range(n-1,-1,-1):
            for j in range(1,d+1):
                if n-i<j: #more days than jobs
                    continue
                rMax = -math.inf
                for k in range(i,n-j+1): #if we finish i:k+1 jobs today
                    rMax=max(rMax,A[k])
                    if j==1:
                        dp[i][j]=rMax
                    else:
                        dp[i][j] = min(dp[i][j],rMax+dp[k+1][j-1])
        return dp[0][d]    

class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        n = len(jobDifficulty)
        
        dp = [[float('inf')] * n + [0] for i in range(d + 1)]
        for i in range(1, d+1):
            for j in range(n - i + 1):
                maxd = 0
                for x in range(j, n - i + 1):
                    maxd = max(maxd, jobDifficulty[x])
                    dp[i][j] = min(dp[i][j], maxd + dp[i - 1][x + 1])
        return dp[d][0] if dp[d][0] < float('inf') else -1

class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        # 1 2 3
      # 6 6
      # 5 6 11 0 11 10 9
    # init
    # dp[j][d+1], if j < d, dp[j][d] = -1, dp[0][0] = 0 
    # transition
    # 0 < k < d, dp[j][k] = min[dp[i][k-1] + max(i..j)] 
    # answer dp[n][d]
    
        n = len(jobDifficulty)
        if n < d:
            return -1
        dp = [[math.inf for _ in range(d + 1)] for _ in range(n+1)]
        dp[0][0] = 0
        
        for j in range(0, n+1):
            for k in range(1,d+1):
                dp[j][k] = math.inf
                mx = 0
                for i in reversed(range(j)):
                    mx = max(mx, jobDifficulty[i])
                    dp[j][k] = min(dp[j][k], dp[i][k-1] + mx)
        print(dp)
        return dp[n][d]