整箱配送（delivery）

题目描述

某物流中心正在试运行一套新的自动配送系统。

每天，配送系统都会生成一份任务清单。工作人员必须根据清单完成一系列运输指令，只有通过最终验收，才能获得当天的配送报酬。

本次任务的终点被标记为 (V) 号站点。

配送车辆从编号为 (0) 的起始站点出发，沿一条单向路线行驶。途中设有编号连续递增的站点，车辆不能倒退。

运输指令

物流中心提供了 (n) 种运输指令。

第 (i) 种指令具有两个参数 $(w_i) 和 (v_i)$。

工作人员可以在途中选择一条当前允许使用的指令。假设执行指令前，车辆位于编号为 (p) 的站点，那么执行该指令后，系统会将车辆送往编号为 (p+w_i) 的站点。

每条指令必须完整执行，中途不能停止。

所有已完成的指令都会被记录到配送日志中。在当天的任务通过最终验收后，每条第 (i) 种指令的记录均可以结算 (v_i) 元报酬。

不过，运输指令并不是都能随意使用。

指令审核

在任务开始前，系统会对每种运输指令进行一次审核。

对于参数为 (x) 的指令，审核人员需要研究以下问题：

将 (x) 个相同的标记平均分成若干个非空小组，要求每组包含的标记数量相同。

审核人员记录所有可能的小组数量。

例如：

当 (x=6) 时，可以分成：

• 1 组，每组 6 个标记；
• 2 组，每组 3 个标记；
• 3 组，每组 2 个标记；
• 6 组，每组 1 个标记。

因此，共有 4 种不同的小组数量。

当 (x=5) 时，只有 2 种不同的小组数量。

审核完成后，系统按以下规定管理指令：

• 如果某种指令恰好对应 2 种不同的小组数量，那么这条指令在本次任务中只能执行一次。
• 其他指令不受执行次数限制。

每种指令的使用次数分别统计。

最终验收

当天的配送任务只有一个验收位置，即 (V) 号站点。

车辆在执行指令时，不能到达编号大于 (V) 的站点。

工作人员可以自行决定指令的执行顺序，也可以不使用某些指令。

但是，只有车辆最终恰好停在 (V) 号站点，整份配送日志才会通过验收。

如果车辆停在其他位置，即使已经完成了若干条运输指令，当天的配送任务也会被判定为失败。

现在，请你帮助物流中心安排运输指令，使任务能够通过验收，并让最终结算的配送报酬尽可能多。

如果不存在任何能够通过验收的方案，输出 -1。

输入格式

第一行包含两个正整数 (n,V)，分别表示运输指令的种类数量以及最终验收站点的编号。

接下来 (n) 行，每行包含两个正整数 $（w_i,v_i)$，表示第 (i) 种运输指令的两个参数。

输出格式

输出一个整数，表示能够通过最终验收时获得的最多配送报酬。

如果无法通过最终验收，输出 -1。

输入输出样例 #1

输入

3 9
2 6
4 7
5 10

输出

17

样例解释

系统提供了三种运输指令。

根据审核结果：

• 第一种指令最多执行一次。
• 第二种指令可以重复执行。
• 第三种指令最多执行一次。

工作人员可以采用以下方案：

首先执行第二种指令，车辆从 0 号站点到达 4 号站点。

随后执行第三种指令，车辆从 4 号站点到达 9 号站点。

车辆恰好到达最终验收站点，任务通过验收。

两条指令的结算报酬分别为 7 元和 10 元，因此最终获得：

$7+10=17$

元。

可以证明，不存在报酬更高的合法方案。

数据范围

对于所有测试数据，保证：

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

测试点编号	层级	n	V	数据特征	标准输出	设计目的
1	弱数据	1	5	重量 1 为非质数，可重复选择	10	检查 1 的判定及完全背包
2			4	只有一件重量 2 的质数物品	-1	检查质数物品不能重复，容量不可达
3			2	质数物品恰好装满	7	检查质数重量的基础 0/1 转移
4	基础数据		12	重量 4 的非质数物品	27	检查非质数物品可以重复选择
5	正常数据	4	10	重量包含 2、4、5、6	30	检查质数 0/1 与非质数完全背包混合
6	边界数据	3	7	可用重量均为偶数	-1	检查无法恰好装满时输出 -1
7	正常数据	4	6	两件独立的重量 3 质数物品	22	检查相同质数重量的不同物品可各选一次
8	较强数据	3	10	单件最高价值低于精确组合价值	55	卡按单项价值直接选择
9	极限价值	1	2000	重量 1、价值 2×10⁹	4000000000000	检查大量重复选择及 long long
10	极限规模	100		重量为 1～100；质数价值为 3w²，其余为 w²	297314	检查最大规模、连续判质、精确可达性和混合转移