Jungle Monster Elimination

LXL finds himself in a dense jungle facing n monsters arranged in a line. The i^th monster (from left to right) has an initial health of \(m_i\). LXL has a musket that fires bullets with a controllable power value \(p\). He will fire exactly \(k\) bullets, and each bullet will have the same power \(p\) (a positive integer that you are to determine).

When LXL fires a bullet at the monster at position \(i\) with power \(p\), the following happens:

• The targeted monster \(i\) loses \(p\) health.
• For every monster to the left (i.e. at position \(j\) where \(j < i\)), it suffers splash damage of \(\max(0, p - (i - j)^2)\).

A monster dies as soon as its health becomes negative. (Note that even after dying, a monster's position remains and can still absorb splash damage from later bullets.)

LXL wants to know the minimum positive integer \(p\) such that by firing exactly \(k\) bullets (each with power \(p\)) it is possible to kill all the monsters. It is allowed to fire more bullets than the minimum required on a particular monster if that helps to deliver extra splash damage to monsters on its left.

Input/Output Example: For instance, if there are 3 monsters with health values [3, 1, 2] and \(k = 3\), one valid strategy is to first shoot the rightmost monster and then use the splash effect to help kill the others, with the minimum \(p = 3\) working.

inputFormat

The first line contains two integers \(n\) and \(k\) (\(1 \leq n \leq 10^5\), \(1 \leq k \leq 10^9\)). The second line contains \(n\) integers \(m_1, m_2, \ldots, m_n\) (\(0 \leq m_i \leq 10^9\)) representing the initial health values of the monsters.

outputFormat

Output a single integer — the minimum positive integer \(p\) such that LXL can kill all monsters by firing exactly \(k\) bullets each with power \(p\).

sample

3 3
3 1 2

3