最大价值正序误用

难度：T2

【知识点：错误复现与回归】

前置知识：已学树、BFS、0/1背包。

题目描述

每件物品最多一次，重量w价值v，容量上限W，不要求装满。两版dp[0..W]均初始0，按输入顺序处理物品，都更新dp[c]=max(dp[c],dp[c-w]+v)。正确版c从W倒到w，故意错误版c从w正到W。按容量0..W输出首个结果不同的位置及两版结果，无差异输出0。

错误规则仅用于本题对照实验，不是推荐算法。

输入格式

第一行n W；随后n行w v。

输出格式

有差异输出c 正确最大值 错误最大值；否则单独0。

样例输入

1 2
1 2

样例输出

2 2 4

样例解释

容量0、1相同；容量2正确只选一次价值2，错误重复选两次价值4。

数据范围

0≤n≤12，0≤W≤40，1≤w≤40，0≤v≤100。