题目大意

在坐标的x轴上有$n$条线段，第i条线段拥有$w_i$的价值。请问选出若干条互不重叠的线段的最大价值是多少？

输入描述：

第一行一个整数$n \leq 2000$，代表线段的条数。

第二行n个整数，代表每条线段中点的横坐标。

第三行n个整数，代表每条线段的半径长度（即整条线段长度的一半）。

第四行n个整数，代表每条线段的价值

样例

输入

7
3 4 6 8 3 2 6
2 3 2 1 3 2 2
2 5 2 5 7 8 3

输出

13