三角洲部队物资分配问题

题目背景

三角洲部队完成了一次突击任务，缴获了 N 箱物资。每箱物资有一个价值和一个重量。部队需要将这些物资装进直升机运走，但直升机的最大载重有限。

队长决定：选择若干箱物资，使得在总重量不超过直升机载重的前提下，总价值尽可能大。

但在三角洲部队有个传统：如果选择了第 i 箱物资，那么第 i-1 箱和第 i+1 箱物资不能同时被选择（相邻物资不能同时装，防止重心不稳）。

题目描述

给定 N 箱物资，每箱物资有两个属性：

• 价值 v[i]
• 重量 w[i]

以及直升机的最大载重 W。

请计算在满足以下条件时的最大总价值：

1. 总重量 ≤ W
2. 任意两箱被选中的物资不能相邻（即不能同时选择 i 和 i+1）

输入格式

第一行包含两个整数 N 和 W，分别表示物资数量和直升机最大载重。

第二行包含 N 个整数，表示每箱物资的价值 v[1], v[2], ..., v[N]。

第三行包含 N 个整数，表示每箱物资的重量 w[1], w[2], ..., w[N]。

输出格式

输出一个整数，表示能获得的最大总价值。

样例

样例输入 1

5 10
6 3 5 4 7
3 2 4 3 5

样例输出 1

11

解释：选择第 2 箱（价值3，重量2）和第 4 箱（价值4，重量3），总重量5≤10，价值7？不对。选择第1箱（6，3）和第3箱（5，4）和第5箱（7，5）：总重量12>10不行。选择第1箱（6，3）和第4箱（4，3）：价值10，重量6≤10。选择第2箱（3，2）和第4箱（4，3）和第？第5箱不能选因为相邻，选择第2箱和第4箱价值7。选择第1箱和第3箱和第5箱重量12>10。最优是选择第2箱（3，2）和第5箱（7，5）？不相邻（2和5不相邻），价值10，重量7。或者第1箱（6，3）和第3箱（5，4）总重量7，价值11！且不相邻（1和3不相邻），输出11。

样例输入 2

4 5
10 1 10 1
3 2 3 2

样例输出 2

11

解释：选择第1箱（10，3）和第3箱（10，3），总重量6>5不行。选择第1箱（10，3）和第4箱（1，2），价值11，重量5≤5，不相邻（1和4不相邻），输出11。

数据范围

• 1 ≤ N ≤ 1000
• 1 ≤ W ≤ 10000
• 1 ≤ v[i] ≤ 100
• 1 ≤ w[i] ≤ 100

提示

这是一个二维动态规划问题，状态需要同时考虑：

• 当前处理到第几个物资
• 当前总重量是多少
• 上一个物资是否被选择