‹ 上一题 下一题 ›

g6-07944. 只选一件 未做

1000 ms 256 MB 测试点 ? 6级·0/1背包GESP-601模型与状态状态与转移

题目描述

小杨这次出门只打算带一件物品:它的重量是 、价值是 ,背包容量为 。这件物品要么整件装进去(得到价值 ),要么不装(得到价值 )。求他能获得的最大价值。

输入格式

第一行两个整数 (保证 )。

第二行两个整数 。

输出格式

一行一个整数,表示最大价值。

样例

输入 1

1 5
3 100

输出 1

100

输入 2

1 5
7 100

输出 2

0

数据范围

,。

输入
输出

            
答案