【模板】01背包

题号：NC226514
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 你有一个背包，最大容量为 $V$ 。现有 $n$ 件物品，第 $i$ 件物品的体积为 $v_i$ ，价值为 $w_i$ 。研究人员提出以下两种装填方案：
${\hspace{20pt}}_\texttt{1.}\,$ 不要求装满背包，求能获得的最大总价值；
${\hspace{20pt}}_\texttt{2.}\,$ 要求最终恰好装满背包，求能获得的最大总价值。若不存在使背包恰好装满的装法，则答案记为 $0$ 。

输入描述:

第一行输入两个整数  和 ，分别表示物品数量与背包容量。 
此后  行，第  行输入两个整数 ，分别表示第  件物品的体积与价值。

输出描述:

输出两行： 
 第一行输出方案  的答案； 
 第二行输出方案  的答案（若无解输出 ）。

示例1

输入

复制

输出

复制

14
9

说明

在该组样例中： 
 选择第 、第  件物品即可获得最大价值 （未装满）； 
 选择第 、第  件物品可使背包体积  恰好装满且价值最大，为 。

示例2

输入

复制

输出

复制

8
0

说明

装第三个物品时总价值最大但是不满，装满背包无解。

备注:

要求  的时间复杂度， 空间复杂度。