408842: GYM103348 D Witches Cauldron I

Double double, toil and trouble... The Weird Sisters are heating ingredients for a new concoction to mix into a big mixing pot, but their cauldron for heating recently broke! They have a list of essences to throw into a cauldron to heat in order, but they only have time to heat the cauldron a certain number of times before they need to cast their spell. Each essence needs to be fully in the cauldron (i.e. cannot be split), and all essences are in liquid form.

The Weird Sisters need to purchase a cauldron big enough to finish the spell in time, but are still economical. Can you help them find the smallest size of cauldron that will help them finish in time?

First line of input are two integers $$$1 \leq n \leq 5 \cdot 10^5$$$ and $$$1 \leq k \leq 10^6$$$, the number of essences that must be heated and the number of times they can heat respectively.

The next line contains $$$n$$$ integers, the volume of each essence $$$1 \leq a_i \leq 10^6$$$ in order that needs to be heated.

One integer $$$v$$$, the volume of cauldron needed to finish heating in $$$k$$$ rounds.

3 1
3 1 2

6

4 2
3 1 2 2

4