题目思路

思路：贪心 + multiset（平衡树）

每个物品中能放至多一个其他的物品，且每个物品只能放在至多一个物品内。

先考虑单位空间价值更大的，让他们内部的空间先被填充。

按照单位空间价值从大到小枚举每个物品，对每个物品找到一个体积小于当前枚举物品的空间的物品。即找到一个小于等于 $x$ 的最大的 $y$ 值。

题目内容

小美是一个收藏家，他喜欢收集各种珍奇的物品。最近，他在旅游时在俄罗斯购买了一些俄罗斯套娃。他深深地被这些绚丽多彩的小玩意吸引住了，每天都会花费大量的时间玩弄它们。随着时间的推移，他逐渐发现将套娃放在其他套娃内是一个有趣的游戏，并决定挑战自己，看看他是否能以最小的成本套上所有的俄罗斯套娃。

具体的，小美有 $n$ 个俄罗斯套娃，第 $i$ 个俄罗斯套娃的大小为 $a_i$ ，内部空间为 $b_i$ ( $b_i\le a_i$ )和一个价值 $c_i$ 。

对于两个俄罗斯套娃 $x$ 和 $y$ ， $x$ 能放入 $y$ 中当且仅当 $a_x\le b_y$ ，且放入后会占据 $y$ 大小为 $a_x$ 的内部空间，即y 的内部空间剩下 $b_y-a_x$ ，每个俄罗斯套娃只能放在另外的一个俄罗斯套娃内，每个俄罗斯套娃内部也只能放一个俄罗斯套娃(当然内部放的这个俄罗斯套娃可以内部还有俄罗斯套娃)。

显然俄罗斯套娃是套的越多越好，如果套完之后俄罗斯套娃 $i$ 还剩 $k$ 的内部空间小美需要付出 $c_i\times k$ 的花费，总花费为所有俄罗斯套娃的花费之和。

现在小美想知道最小的花费为多少？

输入描述

第一行一个正整数 $n$ ，表示俄罗斯套娃的个数

接下来三行每行 $n$ 个整数，分别为

a1,a2,...,an
b1,b2,...,bn
c1,c2,...,cn

$1\le n,a_i,b_i,c_i \le 100000$ ， $b_i\le a_i$

输出描述

输出一个整数表示最小的花费。

样例

输入

3
5 4 3
4 2 2
3 2 1

输出

6

样例解释

将第二个俄罗斯套娃放在第一个里面，第三个不动，这样第一个俄罗斯套娃剩 $0$ 的空间，第二个剩 $2$ ，第三个剩 $2$ 。总花费为 $0*3+2*2+2*1=6$ 。

可以证明这是花费最小的方案。