Minimum Sum of Weekly Maximum Costs

Problem Statement

You are managing a project spanning n consecutive days. You are given an integer array costs of length n, where costs[i] represents the resource cost on day i. You are also given an integer k representing the exact number of contiguous weeks (phases) into which you must divide the project.

Every day must belong to exactly one week, and each week must contain at least one day. The cost of a week is defined as the maximum daily cost within that week. The total project cost is the sum of the costs of all k weeks.

Return the minimum possible total project cost. If it is impossible to partition the project into k weeks, return -1.

Function Signature

def min_weekly_cost(costs: list[int], k: int) -> int:
    pass

Constraints

• 1 <= len(costs) <= 300
• 0 <= costs[i] <= 1000
• 1 <= k <= 100

Examples

Example 1

Input: costs = [6, 2, 4, 1, 5], k = 2
Output: 9
Explanation: 
One optimal partition is [6, 2, 4] and [1, 5].
- Week 1: max(6, 2, 4) = 6
- Week 2: max(1, 5) = 5
Total cost = 6 + 5 = 11.

Another partition is [6] and [2, 4, 1, 5].
- Week 1: max(6) = 6
- Week 2: max(2, 4, 1, 5) = 5
Total cost = 6 + 5 = 11.

Another partition is [6, 2] and [4, 1, 5].
- Week 1: max(6, 2) = 6
- Week 2: max(4, 1, 5) = 5
Total cost = 6 + 5 = 11.

However, partitioning as [6, 2, 4, 1] and [5] gives:
- Week 1: max(6, 2, 4, 1) = 6
- Week 2: max(5) = 5
Total cost = 6 + 5 = 11.
Wait, if costs = [7, 1, 7, 1, 7, 1], what if costs = [6, 2, 8, 1, 5]?
With [6, 2, 4, 1, 5], if partitioned as [6] and [2, 4, 1, 5], sum is 6 + 5 = 11.
Consider costs = [3, 2, 1, 4, 1], k = 3:
Partition: [3], [2, 1], [4, 1] -> max(3) + max(2) + max(4) = 3 + 2 + 4 = 9.

Example 2

Input: costs = [5, 4, 3, 2, 1], k = 2
Output: 9
Explanation: 
Partition into [5] and [4, 3, 2, 1].
- Week 1: max(5) = 5
- Week 2: max(4, 3, 2, 1) = 4
Total cost = 5 + 4 = 9.

Example 3

Input: costs = [7, 7, 7], k = 4
Output: -1
Explanation: 
It is impossible to partition 3 days into 4 non-empty weeks.

Edge Cases

• len(costs) < k: Not enough days for each week to have at least one day; return -1.
• len(costs) == k: Every week has exactly one day; the result is simply the sum of all elements in costs.
• k == 1: The entire array forms a single week; the result is max(costs).