小明有一个演出团，有n(1≤n≤500)个人，他的计划下个月在nyist有一场大型表演，每个人按顺序进场，but，nyist 的人对演出很有要求，演出的人如果身高参差不齐，那么会让人很不爽，所以如果相邻两个人身高差1cm，那么小明会损失p(p≤109)元。所以小明为了减少损失，于是就去搞了个偏方，找了个老中医给他的演出团增高，老中医用他多年的致病经验告诉小明，我手里的仙丹可以给你的人长高，但是只能长高，而且每个人长高的潜能是有限的，1cm好长，但是2cm就不好长了，所以我给你一个人长高kcm，那么你要给我k2 的钱，小明想了想就愉快的答应了。但是他的人很多，他需要一个增高方案，使得他损失最小，但是愚蠢的小明是不可能想出这个方案的，于是他向你求助。
