| Author: | Антон Карабанов | Time limit: | 1 sec | |
| Input file: | Standard input | Memory limit: | 256 Mb | |
| Output file: | Standard output |
Natasha has c cats. One morning, when the cats woke up, they discovered that Natasha had beautifully arranged various objects on the table in a specific order. Naturally, the cats couldn’t resist and jumped onto the table, starting to knock down the objects one by one (starting from the first object).
For a cat to knock down an object with weight wi, it takes wi minutes. After that, the cat moves on to the next available object (in the order they are placed). The cats do not help each other (if one cat finishes earlier, it will simply watch the others knock down the remaining objects). Once all the objects have been moved, the cats will run to wake up Natasha and report their work.
Your task is to determine how long Natasha can keep sleeping.
The first two lines of input contain the natural numbers n and c. The third line contains n natural numbers wi — the weights and order of the objects on the table.
Output a single natural number — the answer to the problem.
1 ≤ c ≤ n ≤ 105
1 ≤ wi ≤ 109
For example, on the table there are five objects with weights 1, 2, 3, 4, and 5, and three cats. The events will unfold as follows:
0 minutes: the cats begin their work: the first cat will knock down the first object weighing 1, the second cat will knock down the second object weighing 2, and the third cat will knock down the third object weighing 3.
1 minute: the first cat has knocked down the object weighing 1 and moves to knock down the object weighing 4.
2 minutes: the second cat has knocked down the object weighing 2 and moves to knock down the object weighing 5.
3 minutes: the third cat has knocked down the object weighing 3 and moves into observation mode, watching the others finish.
5 minutes: the first cat knocks down the object weighing 4 and also starts observing.
7 minutes: the second cat knocks down the object weighing 5. All objects have fallen, and the cats run to wake up Natasha.
| No. | Standard input | Standard output |
|---|---|---|
| 1 | |
|