9345: 融合矿石

输入包含多组测试数据。
输入的第一行包含一个整数 $T$ ($1\le T\le 10$)，表示数据组数。
对于每组测试数据：
第一行包含 $10$ 个整数 v1,v2,v3,...,v10v1,v2,v3,...,v10 (1≤vi≤105,∀i∈[1,10),vi≤vi+11≤vi≤105,∀i∈[1,10),vi≤vi+1)，表示价值体系。
第二行包含两个整数 $n$, $m$ ($1\le n,m\le 3000$)，表示矿石的种类数和背包的最大承重。
接下来 $n$ 行，每行两个整数 ai,biai,bi (0<bi≤ai≤30000<bi≤ai≤3000)，表示一块第 $i$ 种矿石的质量和其中"金辉石"的质量。
保证所有测试数据中 $n$ 的总和 与 $m$ 的总和 都不超过 104104。

对于每组测试数据：
输出一行一个整数，表示最大总价值。