UOJ Logo

NOI.AC

1S 512MB

#1275. 旅行者的背包

统计

题目描述

一个旅行者有一个最多能装$M$公斤的背包,现在有$n$钟物品,它们的重量分别是$w_i$,它们的价值分别是$v_i$元/公斤,求旅行者能获得最大总价值。

输入

第1行:两个整数,$M$背包容量($M \leq 1000$)和N物品数量($N \leq 30$); 第$2$至$N+1$行:每行两个整数$w_i,v_i$,表示每个物品的重量和价值。

输出

一个数,表示最大总价值。

样例输入

100 3
40 2
50 3
70 3

样例输出

300