题目内容

某部门的项目经理，近期手头有 $n$ 个开发任务必须全部完成（不可并行，必须顺序执行）。每个任务 $i$ 有三个属性：

• 持续时间 $duration[i]$：执行该任务需要的时间；
• 截止时间 $deadline[i]$：任务必须在某个时刻前完成才能获得收益；
• 收益 $profit[i]$：若在截止时间前完成，可获得的收益。

任务从时刻 $0$ 开始依次执行。若任务 $i$ 的完成时刻（即开始时刻 $+$ $duration[i]）≤ deadline[i]$，则你获得 $profit[i]$；否则该任务收益为 $0$（任务仍要执行）。他可以任意决定任务的执行顺序，目标是最大化所有任务的总收益。请帮他计算最大可能收益。

输入描述

共有 $4$ 个输入参数：

1. $n$：任务数量（$1 \le n \le 20$），编号 $0$ 到 $n$-$1$。
2. $duration$：长度为 $n$ 的正整数数组，$duration[i] ≤ 1000$。
3. $deadline$：长度为 $n$ 的正整数数组，$deadline[i] ≤ 1000$。
4. $profit$：长度为 $n$ 的正整数数组，$profit[i] ≤ 1000$。

输出描述

输出一个整数，表示能获得的最大总收益。

样例1

输入

3,[2,1,3],[3,2,5],[10,20,30]

输出

50

说明

按顺序任务 $2$ $→$ 任务 $3$ $→$ 任务 $1$ 执行：

• 任务 $2$：时刻 $0$ 开始，持续 $1$，完成于时刻 $1$ $≤$ $2$，收益 $20$；
• 任务 $3$：时刻 $1$开始，持续 $3$，完成于时刻 $4$ $≤$ $5$，收益 $30$；
• 任务 $1$：时刻 $4$ 开始，持续 $2$，完成于时刻 $6$ $>$ $3$，收益 $0$。 总收益 $=$ $20 + 30 + 0 = 50$，此为最大。

样例2

输入

4,[1,2,3,4],[1,3,6,10],[100,200,300,400]

输出

1000

说明

所有任务按原顺序执行均可满足截止时间，总收益为 $100+200+300+400 = 1000$。

样例3

输入

2,[5,5],[4,10],[100,200]

输出

200

说明

• 第一个任务持续时间 $5$，截止时间 $4$，无论如何排序都会超时，收益为 $0$。
• 第二个任务无论何时执行均可在截止前完成，收益 $200$。 故最大收益为 $200$。