#P2149. 拆迁队

    ID: 1172 传统题 1000ms 259MiB 尝试: 569 已通过: 144 难度: 9 上传者: 标签>CF2600提高+/省选-坐标变换最长上升子序列线性 DP离散化树状数组凸包优化 DPCDQ 分治二分查找稀疏状态重置

拆迁队

题目描述

lanxisi 带领着他的拆迁队来整治一个街道。这个街道由 NN 个旧房子组成,从左到右编号为 1∼N1\sim N。每个旧房子 ii 有一个正整数的美观度 AiA_{i}。

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

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

输入格式

第一行有一个整数 NN ,表示旧房子个数。

第二行有 NN 个整数,第 ii 个数 AiA_i 表示旧房子的美观度。

第三行有 NN 个整数,第 ii 个数 BiB_i 表示保留旧房子的赔偿金。

输出格式

第一行输出 22 个整数,表示保留的旧房子数量、总花费的大小。

4
2 1 7 4
1 5 4 3
2 25
6
1 6 3 4 7 7
1 2 1 1 1 9
4 29

数据规模与约定

对于 100%100\% 的数据中,1≤N≤1051\le N\le 10^5,0≤Ai,Bi≤1080\le A_i,B_i\le 10^8。