拆迁队

时间限制:10s      空间限制:259MB

题目描述

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

lanxisi希望整个街道从左到右美观度严格递增,也就是保证Ai<Aji<j)。但是旧的街道明显不符合这个要求,于是lanxisi希望拆迁一些旧房子并在原地建立新房子来满足这一要求。但是与很多拆迁队一样,很多钉子户拒绝拆迁。所以lanxisi希望能保留最多的旧房子来满足某些钉子户,当然,保留一个旧房子需要给房子主人Bi的赔偿金。最后,总花费=整治好以后所有房子美观度之和+赔偿金之和。新的美观值也都必须是正整数。

现在,请你求出lanxisi最多能保留多少旧房子和整治这个街道所需要的最少总花费(当然是在保留旧房子最多这个前提下的)。


输入格式

第一行有1个整数N,表示旧房子个数。第二行有N个整数,第i个数Ai表示旧房子的美观度。第三行有N个整数,第i个数Bi表示保留旧房子的赔偿金。


输出格式

第一行输出2个整数,表示保留的旧房子数量、总花费的大小。【样例输入一】 4 2 1 7 4 1 5 4 3 【样例输入二】 6 1 6 3 4 7 7 1 2 1 1 1 9


样例输入

【样例输出一】
2 25

【样例输出二】
4 29

【数据范围】
100%的数据中,1<=N<=100000,0<=Ai,Bi<=100000000。

样例输出


提示

没有写明提示


题目来源

没有写明来源

Menuappsclose