链接: https://cses.fi/problemset/task/1158

板块: Dynamic Programming

时限: 1.00 s ｜ 内存: 512 MB

题目描述

你在一家书店里，店里出售 $n$ 种不同的书。你知道每本书的价格和页数。

你决定购买书籍的总价不超过 $x$。你能买到的最多页数是多少？每本书最多只能买一次。

输入

第一行输入包含两个整数 $n$ 和 $x$：书的数量和最高总价。

下一行包含 $n$ 个整数 $h_1,h_2,\ldots,h_n$：每本书的价格。

最后一行包含 $n$ 个整数 $s_1,s_2,\ldots,s_n$：每本书的页数。

输出

输出一个整数：最多的页数。

数据范围

$1 \le n \le 1000$ $1 \le x \le 10^5$ $1 \le h_i, s_i \le 1000$

样例输入

4 10
4 8 5 3
5 12 8 1

样例输出

13

说明：可以买第 1 本和第 3 本，价格 $4+5=9$，页数 $5+8=13$。