Start 2023-12-02 00:00:00

1202(01背包练习)

End 2023-12-09 00:00:00
Contest is over.
Now 2025-04-20 01:20:47

A. 0/1背包

Description

一个旅行者有一个最多能用m公斤的背包,现在有n件物品,它们的重量分别是W1,W2,...,Wn,它们的价值分别为C1,C2,...,Cn.若每种物品只有一件求旅行者能获得最大总价值。

Input

Output

Examples

Input

10 4
2  1
3  3
4  5
7  9

Output

12

Submit

Login

Signup
Time Limit 1 second
Memory Limit 128 MB
Submit