题面翻译

题意

约翰是一名潜水寻宝者，他刚刚发现了一艘装满宝藏的海盗沉船。约翰乘坐的船上安装了精密的声呐系统，这套系统可以让约翰确定海底宝藏的位置、深度、包含金币的数量。不巧的是，约翰忘记了携带 GPS 设备，因此无法记录沉船的位置以便将来打捞财宝，只能现在打捞。更糟糕的是，约翰身边只有一瓶压缩空气可用。约翰想使用这唯一的一瓶压缩空气潜入水底，将尽可能多的将金币打捞上来。现在需要你编写一个程序来帮助约翰，以便让他决定应该打捞哪些宝箱从而使得金币数量最大化。

本问题的限制条件如下：

1. 总共有 $n$ 个宝箱，${(d_1,v_1),(d_2,v_2),…,(d_n,v_n)}$，每个二元组表示宝箱的深度和包含的金币数 量。$n$ 最大为 $30$；
2. 压缩空气瓶只能让潜水者在水下保持 $t$ 秒。$t$ 最大为 $1000$；
3. 约翰每次潜水最多只能带上来一个宝箱；
4. 下潜所用时间 $td_i$ 和宝箱的深度 $d_i$ 线性相关：$td_i＝w* d_i$，$w$ 是一个整数常数；
5. 上升所用时间 $ta_i$ 和宝箱的深度 $d_i$ 线性相关：$ta_i＝2w* d_i$，$w$ 是一个整数常数；
6. 由于设备的限制，所有参数均为整数类型。

输入格式

输入包含多组数据，每组数据包含若干整数值。

每组数据的第一行包含两个整数 $t$ 和 $w$，分别表示潜水总时间和整数常数。

第二行表示宝箱的数量。接下来的输入行每行包含两个整数 $d_i$ 和 $v_i$，表示不同宝箱的深度和包含的金币数量。

每两组输入数据之间有一个空行。

输出格式

对于每组测试数据，输出的第一行包含一个整数，表示约翰在给定的条件下能够打捞的金币数量的最大值。

第二行表示能够打捞的宝箱数量。

接下来的每一行表示打捞上来的宝箱的深度及所包含的金币数。宝箱的输出顺序要与输入时给出的顺序一致。

在两组输入数据的输出之间输出一个空行。

题目描述

PDF

输入格式

输出格式

样例 #1

样例输入 #1

210 4
3
10 5
10 1
7 2

样例输出 #1

7
2
10 5
7 2