Tyrell has an array arr, denoting the weights of N burgers. The burgers can be eaten only continously i$.$e in sequence as in arr. What should be the minimum weight eating capacity per day, of Tyrell, to consume all the burgers in $$k$$ days?

Input format $$

$$ The first line will contain the size of an array, N

$$ Next $$N$$ lines will contain N integers denoting array arr.

$$ The last line will contain integer k$.$

Constraints

$1<=$k$<=$N$<=1000$

$1<=$arr$[$i$]<=500$

Examples

Input:

$10$

$1$

$2$

$3$

$4$

$5$

$6$

$7$

$8$

$9$

$10$

$5$

Output:

$15$

Explanation:

k $=5$

arr $=[1,2,3,4,5,6,7,8,9,10]$

$1$st day: $1,2,3,4,5->15$

$2$nd day: $6,7->13$

$3$rd day: $8->8$

$4$th day: $9->9$

$5$th day: $10->10$

Min Cap to eat in a day required $->15$