仓库调拨（transfer）

题目描述

某物资中心正在为一支考察队准备运输物资。

运输箱的最大承重为 (V)，仓库中共有 (n) 种不同的物资。

第 (i) 种物资的重量为 (w_i)，价值为 (v_i)。

由于仓库采用特殊的库存管理制度，每种物资的可调拨数量由其重量决定：

• 如果物资的重量是一个质数，那么该种物资库存充足，可以调拨任意非负整数件。
• 如果物资的重量不是质数，那么该种物资仅有一件，最多只能调拨一次。

特别地，(1) 不是质数。

你可以从仓库中选择若干件物资放入运输箱，也可以不选择任何物资。

要求所有选中物资的总重量不超过 (V)。

请计算运输箱中能够装入的物资的最大总价值。

输入格式

第一行包含两个正整数 (V,n)，分别表示运输箱的最大承重和物资种类数。

接下来 (n) 行，每行包含两个正整数 (w_i,v_i)，分别表示第 (i) 种物资的重量和价值。

输出格式

输出一行一个整数，表示能够获得的最大总价值。

输入输出样例 #1

输入 #1

10 3
2 3
4 9
5 8

输出 #1

18

样例解释

三种物资的重量分别为 (2,4,5)。

其中，重量为 (2) 和 (5) 的物资可以重复选择，重量为 (4) 的物资最多只能选择一次。

一种最优方案是：

• 选择 3 件重量为 2、价值为 3 的物资；
• 选择 1 件重量为 4、价值为 9 的物资。

总重量为：

$2\times3+4=10$

总价值为：

$3\times3+9=18$

因此输出 (18)。

输入输出样例 #2

输入 #2

8 1
4 7

输出 #2

7

样例解释

物资重量为 4，不是质数，因此最多只能选择一件。

虽然运输箱容量为 8，但不能重复选择该物资。

数据范围

对于全部测试数据，保证：

• $(1\le n\le100)$
• $(1\le V\le20000)$
• $(1\le w_i\le20000)$
• $(1\le v_i\le10000)$

不同种类的物资可以具有相同的重量或价值，它们仍然视为不同种类。

如果某种物资的重量超过运输箱容量，则该种物资无法被选择。

时间限制： 建议 1 秒
空间限制： 建议 128 MB