s09193. 启动资金 · 林老师的题库

题目描述

你是一名创业者，初始启动资金为 $w$ 。面前有 $n$ 个项目，项目 $i$ 的启动成本为 $c_{i}$ ，成功后带来利润 $p_{i}$ 。每个项目至多做一次；做项目 $i$ 的前提是当前资金不少于 $c_{i}$ （成本只是门槛，不会被扣除），做完后资金增加 $p_{i}$ 。

你最多做 $k$ 个项目（也可以少做或不做）。求最终资金最大是多少。

第一行三个整数 $n, k, w$ 。

接下来 $n$ 行，第 $i$ 行两个整数 $c_{i}, p_{i}$ 。

一行一个整数，表示最终资金的最大值。

输入

输出

初始资金 $2$ ，能做项目 $1$ （利润 $10$ ）或项目 $3$ （利润 $20$ ）；做项目 $3$ 后资金 $22$ ，此时三个项目都能做，再做项目 $2$ （利润 $100$ ），资金 $122$ 。