IPO

题目描述

力扣即将开始 IPO，为了以更高的价格将股票卖给风险投资公司，希望在 IPO 之前开展一些项目以增加资本。由于资源有限，最多只能完成 $k$ 个不同的项目。

有 $n$ 个项目，第 $i$ 个项目有纯利润 $profits_i$ 和启动它需要的最小资本 $capital_i$。初始资本为 $w$。完成一个项目后，获得的利润会添加到总资本中。

求完成最多 $k$ 个不同项目后，能得到的最大总资本。

输入格式

第一行三个整数 $n, k, w$，分别表示项目数、最多完成的项目数、初始资本。

第二行 $n$ 个整数，表示每个项目的利润 $profits_i$。

第三行 $n$ 个整数，表示每个项目所需的最小资本 $capital_i$。

输出格式

一行一个整数，表示最大总资本。

样例

样例输入 1

3 2 0

1 2 3

0 1 1

样例输出 1

4

样例输入 2

3 3 0

1 2 3

0 1 2

样例输出 2

6

数据范围

• $1 \le k \le 10^5$

• $0 \le w \le 10^9$

• $1 \le n \le 10^5$

• $0 \le profits_i \le 10^4$

• $0 \le capital_i \le 10^9$

答案保证在 32 位有符号整数范围内。

提示

贪心：每一步从当前资本买得起的项目中，选择利润最大的项目完成（大根堆维护利润，项目按所需资本排序）。