g5-09054. 展位排期 · 林老师的题库

题目描述

展馆招展：收到 $n$ 份参展申请，馆内只有 $m$ 个展期时段（ $m$ 可能小于 $n$ ），每个时段只能接纳一个展商。第 $i$ 份申请必须在第 $T_{i}$ 个时段结束前开展才值得，预期收益 $R_{i}$ 。

主办方可以拒绝一些申请。收益总和最多是多少？

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

一行一个整数：收益总和的最大值。

输入

5 3
3 1 2 2 3
5 10 20 30 40

输出

按收益从大到小： $40$ （时段上限 $3$ ）放时段 $3$ ； $30$ （上限 $2$ ）放时段 $2$ ； $20$ （上限 $2$ ）放时段 $1$ ； $10$ （上限 $1$ ）已无空位，拒绝； $5$ （上限 $3$ ）拒绝。总计 $40 + 30 + 20 = 90$ 。

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