#P1485. 火枪打怪

火枪打怪

题目描述

LXL 进入到了一片丛林,结果他发现有 nn 只怪物排成一排站在他面前。LXL 有一杆火枪能对付这些怪物。他知道从左至右数第 ii 只怪物的血量是 mim_i。现在 LXL 可以将一些子弹射向某个怪物。LXL 可以控制他所发射的子弹数量及子弹的威力值。当某个子弹射到第 ii 个怪物,如果这个子弹的威力值为 pp,除了这个怪物会掉 pp 点血以外,它左边的第 jj 个怪物 (j<i)(j<i),也会遭到 max(0,p(ij)2)\max(0, p - (i - j)^2) 的溅射伤害(好神奇的子弹)。当某只怪物的血量小于 00 时,它就死了,但它的尸体还在,即怪物的位置永远不会改变。LXL 希望只用 kk 发子弹,请你求出一个最小的正整数 pp,使 LXL 用 kk 发子弹且每发子弹的威力值为 pp 就可以消灭所有怪物。

输入格式

第一行,两个正整数 n,kn,k

第二行,nn 个正整数,第 ii 个正整数表示从左至右数第 ii 只怪物的血量 mim_i

输出格式

一个正整数,表示子弹的最小威力值 pp

3 1
1 4 5

6

提示

对于 30%30\% 的数据,n300n\leq 300

对于 100%100\% 的数据,n5×105n\leq 5\times 10^5k5×105k\leq 5\times 10^51mi10101\leq m_i\leq 10^{10}