lanxisi 带领着他的拆迁队来整治一个街道。这个街道由 个旧房子组成，从左到右编号为 。每个旧房子 有一个正整数的美观度 。
lanxisi 希望整个街道从左到右美观度严格递增，也就是保证 ，。但是旧的街道明显不符合这个要求，于是 lanxisi 希望拆迁一些旧房子并在原地建立新房子来满足这一要求。但是与很多拆迁队一样，很多钉子户拒绝拆迁。所以 lanxisi 希望能保留最多的旧房子来满足某些钉子户，当然，保留一个旧房子需要给房子主人 的赔偿金。最后，总花费等于整治好以后所有房子美观度之和加上赔偿金之和。注意新的美观值也都必须是正整数。
现在，请你求出 lanxisi 在保留旧房子最多这个前提下，最多能保留多少旧房子和整治这个街道所需要的最少总花费。
