#2149. 拆迁队

lanxisi带领着他的拆迁队来整治一个街道。这个街道由N个旧房子组成，从左到右编号为1..N。每个旧房子i有一

个正整数的美观度Ai。lanxisi希望整个街道从左到右美观度严格递增，也就是保证Ai<Aj（i<j）。但是旧的街道

明显不符合这个要求，于是lanxisi希望拆迁一些旧房子并在原地建立新房子来满足这一要求。但是与很多拆迁队

一样，很多钉子户拒绝拆迁。所以lanxisi希望能保留最多的旧房子来满足某些钉子户，当然，保留一个旧房子需

要给房子主人Bi的赔偿金。最后，总花费=整治好以后所有房子美观度之和+赔偿金之和。新的美观值也都必须是正

整数。现在，请你求出lanxisi最多能保留多少旧房子和整治这个街道所需要的最少总花费（当然是在保留旧房子

最多这个前提下的）。