#P11769. 歌唱练习

歌唱练习

题目背景

2077 年,万众瞩目的天依 v100 声库发布了!

但是要熟悉这套新声库可不是件容易的事。

题目描述

天依制定了一个长为 nn 天的练习计划。天依十分努力,她每天的练习时长必须单调不降。同时,为了保护嗓子,第 ii最多练习 tit_i 个单位时间。每一天练习的效果都是不同的,受到天气等多种因素影响,我们用 wiw_i 量化第 ii 天的练习效果,表示她在第 ii 天每练习一个单位时间会使她的熟悉度提升 wiw_i。注意 wi<0w_i<0 也是可能发生的,或许这天太热她越练越糟。

现在,天依已经查明了 nn 天的天气预报并估算出了每天的 tit_iwiw_i,请问她至多能将她的熟悉度提升多少?

输入格式

第一行包含一个整数 nn,表示天依练习计划的天数。

第二行包含 nn 个整数,第 ii 个整数为 tit_i,表示第 ii 天天依不能超过的练习时长。

第三行包含 nn 个整数,第 ii 个整数为 wiw_i,表示第 ii 天天依每练习一个单位时间的熟悉度增加量。

输出格式

输出一行,包含一个整数,表示天依最多能将她的熟悉度提升的量。

3
3 2 3
2 -1 1
5

提示

样例解释

11 天练习 22 个单位时间,使熟悉度提高 44
22 天练习 22 个单位时间,使熟悉度提高 2-2(降低 22);
33 天练习 33 个单位时间,使熟悉度提高 33
天依的熟悉度总共提高了 55

可以证明,不存在比上述方案更优的选择。

数据规模与约定

本题采用捆绑测试。 仅当你通过了该子任务的全部测试数据才能获得该子任务的分值。

对于 100%100\% 的数据,1n1061\le n\le10^60ti1090\le t_i\le10^91000wi1000-1000\le w_i\le1000

对于不同的子任务,作如下约定:

子任务编号 nn\le tit_i\le 特殊性质 子任务分值
11 1515 1515 1010
22 10910^9
33 100100
44 50005000 50005000
55 10910^9
66 10510^5
77 10610^6 11 55
88 10910^9 1515
99 2020

特殊性质:保证 tit_i[0,109][0,10^9] 中均匀随机生成。