Barr the bear, Kang the Penquin, and Khang the car have just came back from another year of the internationally renowned programming competition, "I own iPads" (IOI), and have, as expected, come back with a shipment of N boxes of iPads, with the i-th box containing B_i iPads. Disembarking from the heavily laden cargo ship, the trio pounce/fly/jump from the ship onto solid ground, and make their way to a little-known resort, Tree Ville.
Despite Tree Ville being located in a desolate area far above the chimney tops, the perpetuators of evil, the Squidzofrenzic Calamari, an evil gang consisting of M squid, has found them!
After 23 hours of effort, the Squidzofrenzic Calamari finally managed to clip Kang's wings, force feed Khang with basic knowledge, and put Barr behind bars!
However, the Squidzofrenzic Calamari have agreed to let the IOI trio go, on one condition, that they sort out the mess of how to split the caches of iPads.
Being a very blur race, the Squidzofrenzic Calamari commander has demanded that the trio come up with a way to split the boxes of iPads among the horde of cephalopods, subject to the following conditions:
(i) To ensure equality, we wish to minimise the maximum number of iPads which any squid receives.
(ii) The amount of iPads in each box is indivisible, as the Squidzofrenzic Calamari are not in possession of machines capable of resealing the boxes, and iPads don't quite survive ten-mile underwater journeys very well.
(iii) To prevent further confusion, the boxes each squid gets must be consecutive (e.g. squid 6 gets boxes 17-42, but not boxes 17, 18, 20 etc.)
"What's this messy lousy formulation of a question. Just use a range tree..." Barr the bear growled and went to hibernate.
"This problem... tsk! Such a Tree Ville problem!" Kang the penquin quipped, and went into hiding in a freezer, never to be seen for the rest of the day.
Khang vanished mysteriously in search of free food after mysteriously saying something about fiascos.
And so, the Squidzofrenzic Calamari have thus an unresolved problem, and have consulted YOU to solve it for them.
The first line of the input will contain two integers N and M (1 ≤ N, M ≤ 100,000).
The next line of the input will contain N integers, with the i-th integer representing B_i (1 ≤ B_i ≤ 1,000).
The output should contain only one integer, representing the maximum number of iPads which any single squid receives.
9 3 1 2 3 4 5 6 7 8 9
17
Dividing the iPads as such: 1 2 3 4 5 / 6 7 / 8 9 would fulfill the stipulated conditions, as any other division would increase number of iPads which the "luckiest" squid received. In this case, that squid is the third squid, which receives 17 iPads.
| Subtask | Score |
|---|---|
| 1 | 100 |
| 2 | 0 |