在一条路上,有 n 棵果树,从左到右编号为 1,2,…,n。小明有 h 个小时的时间,他希望利用这个时间摘到更多的果子。他从 1 出发,向右走(不可往回走),有选择的在一些果树停留一定的时间(是 5 分钟的倍数)摘果子。最后在某一个果树结束摘果子。小明从第 i 个果树到第 i+1 个果树需要走 5*Ti 分钟,在第 i 个果树停留,第一个 5 分钟可以摘到 Fi 个果子,以后每再摘 5 分钟,可以摘到的果子量减少 Di,若减少后的果子量小于 0,则减少后的果子量为 0 。小明想知道自己能获得的最大果子数量,请你帮帮他。
(提示:贪心+优先队列)
第一行一个整数 n,表示果树的个数
第二行一个整数 h,表示小明的空闲时间
第三行有 n 个整数,Fi依次表示每个果树第一个 5 分钟能摘到果子的数量
第四行有 n 个整数,Di依次表示以后的每5分钟摘果子数量比前一个 5 分钟摘果子数量减少的数量
第五行有 n-1 个整数,Ti表示由第 i 个果树到第 i+1 个果树需要花 5 *Ti 分钟的路程
输出只有一行,表示小明最多能摘果子的数量。
数据范围
对于所有数据,2<=n<100,1<=h<=20,1<=Fi<=10^9,0<=Di<=10^9。
样例解释
在第 1 个果树摘 15 分钟,共摘得 4+3+2=9 个果子;
在第 2 个果树摘 10 分钟,共摘得 5+3=8个果子;
在第 3 个果树摘 20 分钟,共摘得 6+5+4+3=18 个果子;
从第 1 个果树走到第 2 个果树,从第 2 个果树走到第 3 个果树,共用时间 15 分钟。
共得 35 个果子,并且这是最多的数量。