Description

LXL enters a jungle and finds $n$ monsters standing in a line in front of him. LXL has a musket to deal with these monsters. He knows that the health of the $i$-th monster from left to right is $m_i$. Now LXL can shoot some bullets at certain monsters. LXL can control both the number of bullets he fires and the power of each bullet. When a bullet hits the $i$-th monster with power $p$, besides that monster losing $p$ health, the monster at position $j$ to its left (where $j < i$) also takes splash damage of $\max(0, p - (i - j)^2)$ (what a magical bullet). When a monster’s health becomes less than $0$, it dies, but its body remains, i.e., the positions of the monsters never change. LXL wants to use exactly $k$ bullets. Please find the smallest positive integer $p$ such that LXL can eliminate all monsters by firing $k$ bullets, each with power $p$.

Input Format

The first line contains two positive integers $n, k$.

The second line contains $n$ positive integers, where the $i$-th integer denotes the health $m_i$ of the $i$-th monster from left to right.

Output Format

Output a single integer, the minimal bullet power $p$.

3 1
1 4 5

6

Hint

For $30\%$ of the testdata, $n \leq 300$.

For $100\%$ of the testdata, $n \leq 5 \times 10^5$, $k \leq 5 \times 10^5$, $1 \leq m_i \leq 10^{10}$.

Translated by ChatGPT 5