j01684. 恰好装满的最大价值

题目描述

有 $n$ 件物品，第 $i$ 件的体积是 $w_{i}$ 、价值是 $v_{i}$ ，每件至多选一次。

请选若干件物品使总体积恰好为 $V$ ，并让价值总和尽量大。

特别地：如果无论如何都凑不出恰好 $V$ 的总体积，请输出 -1。

第一行两个整数 $n$ 和 $V$ 。

接下来 $n$ 行，每行两个整数 $w_{i}$ 和 $v_{i}$ ，依次表示第 $i$ 件物品的体积与价值。

一行一个整数：能凑出恰好 $V$ 时输出最大价值总和；凑不出时输出 -1。

输入

输出

恰好凑出体积 $5$ 的方案是第 1 + 2 件（ $2 + 3 = 5$ ），价值 $3 + 2 = 5$ 。

其他方案：第 1 + 3 件体积 $6$ 、第 2 + 3 件体积 $7$ 、三件为 $9$ ——都不等于 $5$ ；单件也都不是 $5$ 。