不可分割的背包问题

题目描述

暑假打工：小明放暑假了，想赚点零花钱，于是想去打工，现在有n份零工，每份零工的时间花费是 $t_1...t_n$ 小时，每份零工的工钱是 $w_1...w_n$元，小明想每天只工作k小时，问小明该如何选择这些零工，才能使得自己的每天收入最高？

输入格式

输入第一行为 $n$( $n\le 10$ )和 $k$ ( $k\le 300$ )，表示有 $n$ 份工作，工作总时间为 $k$ 小时，接下来有 $n$ 行，每行两个整数 $t_i$ 和 $w_i$，表示第 $i$ 项工作的时间花费和工钱。

输出格式

输出为一行，即小明每天所能拿到的最多工钱。

3 10
8 8
4 3
6 5

8

提示

（暂无提示）

来源

童程童美