小明是一家店铺的专职外卖员。小明每天会接到很多不同地方的n个外卖订单,其中第i个订单会在si时刻下单,花费小明t时间往返,并赚取ai元酬劳。小明每次只能送1单外卖,订单一旦错过就会被派给其他外卖员,
如果小明提前知道了今天的全部订单,请你帮小明选择最优的接单方式,使得今天赚取的酬劳最多
对于每一组数据,包含4行数据
第一行是外卖订单数: n。
第二行有n个数字si(i=1,2,3....,n)表示第i的订单的下单时刻为Si。
第三行有n个数字t_i(i=1,2,3....,n)表示完成第i的订单的花费时间为ti。
第四行有n个数字ai(i=1,2,3....,n)表示完成第i的订单的收益为ai。
数据保证: si≤s2≤s3≤....≤sn
1≤n≤50000,1≤siti,ai≤109
输出一个整数,表示小明今天最多可赚取的酬劳。
输入
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时刻以及之前的订单
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.