P1485 火枪打怪

LXL 进入到了一片丛林,结果他发现有 $n$ 只怪物排成一排站在他面前。LXL 有一杆火枪能对付这些怪物。他知道从左至右数第 $i$ 只怪物的血量是 $m_i$。现在 LXL 可以将一些子弹射向某个怪物。LXL 可以控制他所发射的子弹数量及子弹的威力值。当某个子弹射到第 $i$ 个怪物，如果这个子弹的威力值为 $p$，除了这个怪物会掉 $p$ 点血以外，它左边的第 $j$ 个怪物 $(j

无

无

对于 $30\%$ 的数据，$n\leq 300$。 对于 $100\%$ 的数据，$n\leq 5\times 10^5$，$k\leq 5\times 10^5$，$1\leq m_i\leq 10^{10}$。