1254. Minimum Difficulty of a Job Schedule

You must finish jobs in order over exactly d days, doing at least one job each day. A day's difficulty is the maximum difficulty among the jobs done that day, and the schedule's difficulty is the sum over days. Return the minimum possible schedule difficulty, or -1 if fewer jobs than days makes it impossible. The input is JSON {jobDifficulty, d}.

Input: JSON {jobDifficulty, d}.

Output: Integer — the minimum schedule difficulty, or -1.

Examples

Input: {"jobDifficulty":[6,5,4,3,2,1],"d":2}
Output: 7
Explanation: Do the first five jobs on day 1, the last on day 2.

Input: {"jobDifficulty":[9,9,9],"d":4}
Output: -1
Explanation: Fewer jobs than days.

Input: {"jobDifficulty":[1,1,1],"d":3}
Output: 3
Explanation: One job per day.

Constraints

• 1<=n<=300
• 1<=d<=10

Asked by