j01667. 相邻互斥背包 未做

小店货架上有一排 $n$ 件商品，按编号 $1\sim n$ 从左到右摆放。第 $i$ 件商品的费用是 $w_i$、价值是 $v_i$。

小 P 想买下其中若干件，但店长立了一条奇怪的规矩：相邻编号的商品不能同时买（买了第 $i$ 件，第 $i-1$ 件和第 $i+1$ 件就都不能买）。

小 P 一共只有 $V$ 元钱，在总费用不超过 $V$ 的前提下，他希望买到的商品价值总和尽量大。

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

接下来 $n$ 行，每行两个整数 $w_i$ 和 $v_i$，依次表示第 $i$ 件商品的费用与价值。

一行一个整数，表示在费用不超过 $V$、且不相邻同时购买的前提下，能买到的最大价值总和。

只买第 1 件：费用 $2\le 5$，价值 $3$，是最优选择。

• 买第 $1+3$ 件：费用 $2+4=6>5$ 超预算；
• 买第 $2+3$ 件：虽然费用 $7>5$ 超预算，且第 2、3 件相邻；
• 单买第 2 件价值 $2$、单买第 3 件价值 $1$，都不如第 1 件。

• $1\le n\le 100$
• $1\le V\le 5000$
• $0\le w_i\le 5000$
• $-5000\le v_i\le 5000$