题目描述
个任务，每个任务的加工时长均为 分钟；任务 的截止时刻为 ，完成后获得报酬 。任务之间有前置关系： 是任务 的直接前置任务编号， 表示没有前置。保证所有前置关系构成一片等长任务路径森林：每个任务至多一个直接前置，也至多一个直接后继，且不成环；一条任务路径指一条极大的前驱后继链；所有任务路径的长度（任务个数）相同，且同一条任务路径上所有任务的截止时刻相同。
接单以整条任务路径为单位：接下路径上任何一个任务，就必须接下这条路径的全部任务，要么整条全接、要么整条全不接。机器从时刻 开始单线程加工，同一时刻只能加工一个任务，加工不可中断；每个被接任务的完成时刻不得超过它的截止时刻，路径内任务按前置顺序加工。
求能获得的报酬总和的最大值。
输入格式
第一行一个整数 。
接下来 行，第 行三个整数 。
输出格式
一行一个整数，表示报酬总和的最大值。
样例 1
样例
输入
6 5 2 0 5 9 1 5 8 0 5 3 3 4 1 0 4 4 5
输出
22
三条任务路径：（总时长 、总报酬 、截止 ）、（总时长 、总报酬 、截止 ）、（总时长 、总报酬 、截止 ）。按截止从早到晚接：先接 （总时长 ），再接 （总时长 ）；到 时总时长 超过截止 的检查，退掉总报酬最小的路径 （报酬 ），总时长回到 。最终保留 与 ，总报酬 。
样例 2
输入
4 1 5 0 1 9 1 4 6 0 4 2 3
输出
8
路径 总时长 ，整条无法在截止前完成，只能整条放弃；接路径 得报酬 。
数据范围
；； 且 ；前置关系构成等长任务路径森林，同一条任务路径上所有任务的 相同。答案可能超过 位整数范围。