You are given n problems of varying difficulty as homework. This homework is to be submitted in exactly h days of the holidays.

The problems are given to you in an order and must be submitted in order. That is, before solving the problem at index q, all problems at index p, where p < q should be finished.

You must submit atleast 1 problem every day, including on the last day. The teacher is a sadist and does not allow for finishing the homework early.

The difficulty of a day is the difficulty of the most difficult problem solved on that day. The difficulty of the holidays is the sum of difficulty of all days.

Optimize the way you solve the problems and return the minimum possible difficulty with which you can spend your holidays. If it is not possible to solve the problems in a way that satisfies the constraints, return -1.

1 <= n <= 750 [You may get atmost 750 problems as homework]
0 <= di <= 1000 [The difficulty of each problem is an integer between 0 and 1000 (inclusive) ]
1 <= h <= 30 [The holidays are long and may last upto 30 days (inclusive) ]

Example1:
problems = [3,5,7,2,1,8,3,3,3] h = 4
day1 = 3,5,7,2,1,8 [8]
day2 = 3 [3]
day3 = 3 [3]
day4 = 3 [3]
answer = 8 + 3 + 3 + 3 = 17
This is the minimum difficulty of the holidays

Example2:
problems = [3,1,1,1,8] h = 3
day1 = 3 [3]
day2 = 1,1,1 [1]
day3 = 8 [8]
answer = 3 + 1 + 8 = 12

Example3:
problems = [1,1,1,1] h = 5
The answer is -1 because you cannot submit problems on each day, one day will be free.

Example4:
problems = [1,1,1,2,1,1,9] h = 2
answer = 10

Example5:
problems = [1,2,3,1,2,3,1,2,3] h = 8
answer = 16