Split Array Largest Sum

hard

1. Given an array nums which consists of non-negative integers and an integer m, you can split the array into m non-empty continuous subarrays.
2. Write an algorithm to minimize the largest sum among these m subarrays.

Input Format

Input is managed for you

Output Format

Output is managed for you

Constraints

1 &lt;= nums.length &lt;= 1000
0 &lt;= nums[i] &lt;= 10^6
1 &lt;= m &lt;= nums.length

Notice

Try First, Check Solution later

1. You should first read the question and watch the question video.
2. Think of a solution approach, then try and submit the question on editor tab.
3. We strongly advise you to watch the solution video for prescribed approach.

Example

Input

5
7 2 5 10 8
2

Output

Allocate Minimum Number Of Pages

Count The Triplets