Consider a non empty array inarr of positive integers containing atleast two elements and an integer innum where 0<num. Identify and print an integer outnum as per the logic below:

1. Identify the various combinations in which the elements of inarr can be divided into maximum of innum groups such that:

1. each element occurs exactly in one group and
2. each group will contain elements which are adjacent to each other in inarr.

2. For each combination identify the group whose sum of elements is maximum.

3. Assign the minimum value from the above identified maximum sums to outnum.

Input

Elements of inarr separated by comma

Integer value innum

Output

Print outnum

Sample Input 1

5, 10, 30, 20, 15
3

Sample Output 1

35

Sample Input 2

10, 20, 30, 40
2

Sample Output 2

60