题目描述

本题来自一本通 C++ 编程语言入门 基础算法 第九章 动态规划（pid 2003）。

小佳佳的父亲一直在努力工作。他最近一段时期的工作情况描述如下：
小佳佳的父亲一开始拥有钱的数量为 M，一共有 N 项工作，做完第 i 项工作需要花掉的钱数为 D_i ，同时，做完第 i 项工作后能马上获得钱数为C_i 的奖励，当然C_i 一定会小于 D_i，同一项工作只能做一次。特别说明：小佳佳的父亲不能借钱来做某项工作。
现在给出每项工作的数据，小佳佳想知道他父亲最多能做完多少项工作？

输入格式

第一行两个正整数 N,M，表示工作项目数和小佳佳的父亲一开始拥有钱的数量。
第二行有 N 个正整数 D_i, 第 i 个数对应第 i 项工作。
第三行有 N 个非负整数 C_i, 第 i 个数对应第 i 项工作。

输出格式

一个整数，表示最多能做完的工作项目数。

4 13
5 8 2 1
2 0 0 0

3

提示

样例解释：他可以选择 1, 3, 4 工作项目。
【数据范围】
对于 30% 的数据， 1≤ N ≤ 10；
对于另外 10% 的数据， C_i = 0；
对于另外 10% 的数据， D_i - C_i = 1；
对于另外 30% 的数据， 1≤ N ≤ 1000；
对于 100% 的数据， 1≤ N ≤ 5000；
对于所有数据，0≤ C_i < D_i ≤ 5000, 1≤ D_i,M ≤ 5000。

来源

一本通基础-动态规划 编程题