F.A.Q
Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist
 
     C/C++/Java Exams     
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
    DIY | Web-DIY beta
Author ID 
Password 
 Register new ID

融合矿石

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 489    Accepted Submission(s): 211


Problem Description
在遥远的古代,有一个被遗忘的王国,其地下埋藏着无尽的宝藏。这些宝藏并非普通的金银财宝,而是由一种特殊合金制成,合金中蕴含着不同比例的"金辉石"。

王国中散落着 $n$ 种不同的矿石,每种矿石的数量都是 **无限** 的。对于第 $i$ 种矿石,一块该矿石的质量为 $a_i$,其中含有"金辉石"的质量为 $b_i$ ($0\lt b_i\le a_i$) 。探险家们发现,矿石之间可以相互融合:将两块矿石融合后,会得到一块新的矿石,其质量为两者质量之和,含有"金辉石"的质量也是两者之和。融合后的矿石仍可与其他矿石融合。

为了评估这些矿石的价值,探险家们制定了一套价值体系:对于任意一块矿石,其 **单位质量** 的价值由其中"金辉石"的占比 $\frac{b}{a}$ 决定。这个价值体系由 $10$ 个整数 $v_1,v_2,v_3,\cdots,v_{10}$ 组成,表示对于"金辉石"占比 $\in (\frac{i-1}{10},\frac{i}{10}]$ 的矿石,其单位质量的价值是 $v_i$ 。保证随着"金辉石"占比的增大,矿石的单位价值是单调不减的,即 $\forall i\in [1,10),v_i\le v_{i+1}$。

现在,探险家们携带了一个最大承重为 $m$ 的背包,在进行任意次融合矿石的操作后,选择总质量不超过 $m$ 的矿石装入背包中,请你计算背包内矿石的最大总价值。
 

Input
输入包含多组测试数据。

输入的第一行包含一个整数 $T$ ($1\le T \le 10$),表示数据组数。

对于每组测试数据:

第一行包含 $10$ 个整数 $v_1,v_2,v_3,...,v_{10}$ ($1 \le v_i \le 10^5, \forall i\in [1,10),v_i\le v_{i+1}$),表示价值体系。

第二行包含两个整数 $n$, $m$ ($1\le n,m\le 3000$),表示矿石的种类数和背包的最大承重。

接下来 $n$ 行,每行两个整数 $a_i,b_i$ ($0 \lt b_i\le a_i \le 3000$),表示一块第 $i$ 种矿石的质量和其中"金辉石"的质量。

保证所有测试数据中 $n$ 的总和 与 $m$ 的总和 都不超过 $10^4$。
 

Output
对于每组测试数据:

输出一行一个整数,表示最大总价值。
 

Sample Input
1 1 1 1 1 1 3 3 3 4 5 2 10 4 2 6 5
 

Sample Output
30
 

Source
 

Statistic | Submit | Discuss | Note
Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2024 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
Total 0.000000(s) query 1, Server time : 2024-11-22 08:23:40, Gzip enabled