Mr. Reynolds is hosting a pizza party for his algorithms class after the whole class managed to score above 50 percent. There are $$$N$$$ $$$(1 \leq N \leq 10^5)$$$ students in his class, and each of them wants a certain number of slices of pizza. Unfortunately, Mr. Reynolds has a limited budget and has already purchased $$$K$$$ $$$(1 \leq K \leq 10^5)$$$ pizzas, but he has not cut them up into slices yet.

The process of receiving pizza is as follows: the students will line up in a single file line, and each student will demand $$$d_i$$$ slices of pizza ($$$1 \leq i \leq N, 1 \leq d_i \leq 10^6$$$) in that order. Then, if the current pizza has at least $$$d_i$$$ slices of pizza left, Mr. Reynolds will give the student that amount. Otherwise, Mr. Reynolds will eat the remainder of the pizza himself and open up a fresh new pizza for the student.

Mr. Reynolds is clairvoyant and happens to know the values of $$$d_i$$$, and the order in which the students will line up. Please help Mr. Reynolds figure out the minimum number of slices each pizza needs to have so that all children get their desired amount of pizza. Note that all pizzas must have the same number of slices, and it is okay if pizza is left over.