Minimize Maximum Group Sum

You are given an integer array nums and an integer k. Partition every element of nums into exactly k groups. Each element must be placed in exactly one group and cannot be split. A group is allowed to be empty.

The cost of a partition is the largest sum of any single group. Return the minimum possible cost over all partitions of nums into k groups.

Examples

Example 1

Input: nums = [8,15,10,20,8], k = 2
Output: 31
Explanation: One optimal partition is [8,15,8] and [10,20].
- Group 1 has sum 8 + 15 + 8 = 31.
- Group 2 has sum 10 + 20 = 30.
The cost is max(31, 30) = 31. No partition achieves a cost below 31.

Example 2

Input: nums = [6,1,3,2,2,4,1,2], k = 3
Output: 7
Explanation: One optimal partition is [6,1], [3,2,2], and [4,1,2].
- Group 1 has sum 6 + 1 = 7.
- Group 2 has sum 3 + 2 + 2 = 7.
- Group 3 has sum 4 + 1 + 2 = 7.
The cost is max(7, 7, 7) = 7. No partition achieves a cost below 7.