题目描述

一个旅行者有一个最多能装$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