思路

本质是给定若干个区间，选出权值和最大的不重叠区间。

如果权值和全部等于1 ， 那么就是选出最多不重叠区间，原题：435. 无重叠区间

但是本题是带权值的，所以需要使用动态规划，见P1019. 2022.9.21-互不重叠线段的最大价值

题目描述

小明是一家店铺的专职外卖员。小明每天会接到很多不同地方的n个外卖订单，其中第$i$个订单会在$s_i$时刻下单，花费小明$t$时间往返，并赚取$a_i$元酬劳。小明每次只能送$1$单外卖，订单一旦错过就会被派给其他外卖员，

如果小明提前知道了今天的全部订单，请你帮小明选择最优的接单方式，使得今天赚取的酬劳最多

输出描述

对于每一组数据，包含$4$行数据

第一行是外卖订单数: $n$。

第二行有$n$个数字$s_i(i=1,2,3....,n)$表示第$i$的订单的下单时刻为$S_i$。

第三行有$n$个数字t_i(i=1,2,3....,n)表示完成第$i$的订单的花费时间为$t_i$。

第四行有$n$个数字$a_i(i=1,2,3....,n)$表示完成第$i$的订单的收益为$a_i$。

数据保证: $s_i \leq s_2 \leq s_3 \leq.... \leq s_n$

$1 \leq n \leq 50000,1 \leq s_i t_i,a_i \leq 10^9$

输出描述

输出一个整数，表示小明今天最多可赚取的酬劳。

样例

输入

5
1 3 6 7 11
4 3 4 3 9
2 5 5 3 4

输出

14

提示

小明选择接$2、3、5$单可以赶在下一单到来前结束当前订单，并可以赚取$14$元。

提示，如果小明在$t$时刻返回，她可以接包括$t$时刻以及之后到来的订单，但不能接$t-1$时刻以及之前的订单