#P1019. 2022.9.21-互不重叠线段的最大价值

2022.9.21-互不重叠线段的最大价值

题目大意

在坐标的x轴上有nn条线段,第i条线段拥有wiw_i的价值。请问选出若干条互不重叠的线段的最大价值是多少?

输入描述:

第一行一个整数n2000n \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