g5-09061. 甜品店旺季 · 林老师的题库

题目描述

甜品店旺季有 $n$ 个订单，店里共安排 $n$ 个制作时段，每个时段只能完成一个订单。第 $i$ 个订单必须在第 $T_{i}$ 个时段结束前完成才能拿到报酬 $R_{i}$ （完成时段的编号不超过 $T_{i}$ 即可）。

老板可以放弃一些订单。他能拿到的报酬总和最多是多少？

第一行一个整数 $n$ 。第二行 $n$ 个整数 $T_{1}, \dots, T_{n}$ 。第三行 $n$ 个整数 $R_{1}, \dots, R_{n}$ 。

一行一个整数：报酬总和的最大值。

输入

4
4 2 2 1
10 30 20 40

输出

按报酬从大到小安排： $40$ （期限 $1$ ）放时段 $1$ ； $30$ （期限 $2$ ）放时段 $2$ ； $20$ （期限 $2$ ）的时段 $1, 2$ 都已被占，放弃； $10$ （期限 $4$ ）放时段 $4$ 。总计 $40 + 30 + 10 = 80$ 。

$1 \leq n \leq 500$ ， $1 \leq T_{i} \leq n$ ， $1 \leq R_{i} \leq 1000$ 。