融合矿石

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

2024“钉耙编程”中国大学生算法设计超级联赛（9）