UVA990 Diving for Gold

## 题意 约翰是一名潜水寻宝者，他刚刚发现了一艘装满宝藏的海盗沉船。约翰乘坐的船上安装了精密的声呐系统，这套系统可以让约翰确定海底宝藏的位置、深度、包含金币的数量。不巧的是，约翰忘记了携带 ``GPS`` 设备，因此无法记录沉船的位置以便将来打捞财宝，只能现在打捞。更糟糕的是，约翰身边只有一瓶压缩空气可用。约翰想使用这唯一的一瓶压缩空气潜入水底，将尽可能多的将金币打捞上来。现在需要你编写一个程序来帮助约翰，以便让他决定应该打捞哪些宝箱从而使得金币数量最大化。 本问题的限制条件如下： 1. 总共有 $n$ 个宝箱，${(d_1,v_1),(d_2,v_2),…,(d_n,v_n)}$，每个二元组表示宝箱的深度和包含的金币数 量。$n$ 最大为 $30$； 1. 压缩空气瓶只能让潜水者在水下保持 $t$ 秒。$t$ 最大为 $1000$； 1. 约翰每次潜水最多只能带上来一个宝箱； 1. 下潜所用时间 $td_i$ 和宝箱的深度 $d_i$ 线性相关：$td_i＝w* d_i$，$w$ 是一个整数常数； 1. 上升所用时间 $ta_i$ 和宝箱的深度 $d_i$ 线性相关：$ta_i＝2w* d_i$，$w $ 是一个整数常数； 1. 由于设备的限制，所有参数均为整数类型。

输入包含多组数据，每组数据包含若干整数值。 每组数据的第一行包含两个整数 $t$ 和 $w$，分别表示潜水总时间和整数常数。 第二行表示宝箱的数量。接下来的输入行每行包含两个整数 $d_i$ 和 $v_i$，表示不同宝箱的深度和包含的金币数量。 每两组输入数据之间有一个空行。

对于每组测试数据，输出的第一行包含一个整数，表示约翰在给定的条件下能够打捞的金币数量的最大值。 第二行表示能够打捞的宝箱数量。 接下来的每一行表示打捞上来的宝箱的深度及所包含的金币数。宝箱的输出顺序要与输入时给出的顺序一致。 在两组输入数据的输出之间输出一个空行。