OI题库

【题目描述】

我们的国王赢得了一场血腥的战争，因此现在整片大陆都是我们的了。这片大陆的特殊之处在于这里有许多美丽的纯金雕像。国王希望往他的宫殿里带回尽可能多的黄金。我们已经发现了那里有N种雕像，并且——不可思议的——每种雕像都有无数个。每一座第i种雕像的重量为W[i]个单位，并且占据V[i]个单位的体积。国王希望最大化他带回宫殿的金子总数。我们可以我们可以使用S个袋子来完成这一目标，每个的容量都是Y。所有的袋子都独立地装入纯金雕像，不能把雕像切开。不过，可以把两个袋子缝在一起，需要消耗C个单位的黄金。把三个袋子缝在一起需要消耗2*C，因为这需要两次缝合，以此类推。你的任务是找出国王最多可以获得多少金子，也就是说，带回去金子的总重量减去缝合袋子的花费。

【输入格式】

输入包含多组数据。

输入文件的第一行有一个整数T，即数据组数。

接下来是T组数据。

每组数据格式如下：

第一行：N S Y C

接下来有N行，每行含两个整数W[i]和V[i]。

【输出格式】

输出一个整数，即最多能获得多少金子。

【样例输入】

2

2 5 3 1

1 2

5 7

2 5 3 1

1 2

7 5

【样例输出】

6

17

【提示】

1<=S<=1000

1<=Y<=1000000000

1<=N<=1000

1<=W[i]<=100

1<=V[i]<=18

输出不超过64位带符号整数范围。

1<=T<=20

所有的W[i]和V[i]是素数或1.

【来源】

SPOJ 699 Huge Knap Sack

ByteCode 2006