|
||||||||||
融合矿石Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)Total Submission(s): 480 Accepted Submission(s): 208 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
Sample Output
Source | ||||||||||
|