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

Source: leetcode | Difficulty: MEDIUM
Tags: Dynamic programming

Data structures

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 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 remain == 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
		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, A: List[int], d: int) -> int:
		n = len(A)
		if d > n:
			return -1
		dp = [[math.inf] * (d + 1) for _ in range(n)]
		for i in range(n - 1, -1, -1):
			for j in range(1, d + 1):
				if n - i < j:
					continue
				rMax = -math.inf
				for k in range(i, n - j + 1):
					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)
		if n < d:
			return -1
		dp = [[float('inf')] * (n + 1) for _ in range(d + 1)]
		dp[0][0] = 0
		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):
					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]


class Solution:

	def minDifficulty(self, difficulty: List[int], d: int) -> int:
		if d > len(difficulty):
			return -1
		n = len(difficulty)
		dp = [[float('inf')] * (n + 1) for _ in range(d + 1)]
		dp[0][0] = 0
		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:
		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
				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)
		return dp[-1][-1] if dp[-1][-1] < 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:
		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 = 1000000.0
		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)
		if n < d:
			return -1
		dp = [[float('inf')] * (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):
				max_difficulty = 0
				j = i - 1
				while j >= k - 1:
					max_difficulty = max(max_difficulty, jobDifficulty[j])
					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, A: List[int], d: int) -> int:
		seen = {}

		def func(sidx, d):
			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 = [[-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)
		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])
		res = [float('inf')]

		def search(i, j, val):
			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)


class Solution:

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

		def func(sidx, d):
			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, 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]
				elif 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]


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, J: List[int], d: int) -> int:
		if len(J) < d:
			return -1
		dp = {}
		for (i, job) in enumerate(J):
			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:
		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):
			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, 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:
		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)


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, 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, jD: List[int], d: int) -> int:
		if len(jD) < d:
			return -1
		memo = {}

		def dp(memo, 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)):
				cur = max(cur, jD[j])
				x = dp(memo, jD, j + 1, 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:
		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


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:
		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


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)


from functools import lru_cache

class Solution:

	def minDifficulty(self, A, d):
		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))

		def helper(jobD, n, d, dp):
			if n < d:
				return -1
			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]))
			return dp[d][n]
		r = helper(jobDifficulty, n, d, 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


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):
		njobs = len(jobDifficulty)
		if njobs < d:
			return -1
		dp = [[float('inf')] * njobs for _ in range(d)]
		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:
		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: List[int], d: int) -> int:
		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):
				if k == 1:
					dp[i][k] = max(jobDifficulty[:i + 1])
					continue
				if k > i + 1 or (i == 0 and k == 1):
					continue
				mind = 10000
				for j in range(0, i):
					mind = min(dp[j][k - 1] + max(jobDifficulty[j + 1:i + 1]), mind)
				dp[i][k] = mind
		print(dp)
		return dp[-1][-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):
			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:
		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 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)
		return dp[-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):
					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]


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 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]


from queue import PriorityQueue

class Solution:

	def getminSum(self, jobDifficulty, d, memo, 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
		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
		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


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, 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
		dp = [[-1 for _ in range(num_jobs)] for _ in range(d)]
		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
		for day in range(1, d):
			stack = []
			for job in range(day, num_jobs):
				dp[day][job] = dp[day - 1][job - 1] + jobDifficulty[job]
				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:

		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)
			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]


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)
		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
		elif d == n:
			return sum(jobDifficulty)
		else:
			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):
						futureCost = dp[i + 1][k + 1]
						todayCost = max(jobDifficulty[j:k + 1])
						dp[i][j] = min(dp[i][j], todayCost + futureCost)
			return dp[0][0]


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]


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, 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


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:
		(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 _tmp(self):
		jd = jobDifficulty
		inf = 1000000000.0
		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 = 1000000000.0
		l = len(jd)
		if l < d:
			return -1
		opt = [[0] * (l - d_) + [inf] * d_ for d_ in range(d)]
		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
		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)]
		fdm = [[None] * m for _ in range(d + 1)]
		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]
		for di in range(2, d + 1):
			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])
		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


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:
		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])):
					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
		return grid[-1][0]


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)
		return dp[-1][-1]


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])
		for i in range(1, d):
			for j in range(i, N):
				last_dayD = jD[j]
				for k in range(j - 1, i - 2, -1):
					last_dayD = max(last_dayD, jD[k + 1])
					dp[i][j] = min(dp[i][j], dp[i - 1][k] + last_dayD)
		return dp[d - 1][N - 1]


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, 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)]
		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 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, 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)
		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)):
						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)
		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)]
		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
		for day in range(1, d):
			for job in range(day, num_jobs):
				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]


class Solution:

	def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
		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]