兴华超市今天关门了，川川超市取而代之。
川川超市里，有nnn种不同的生活用品。川川的商品一向物美价廉，对于第iii种生活用品，其价格为cic_ici，实用度为viv_ivi。
作为这家超市的第一个顾客，你正准备要把川川超市
的用品狠狠购买，然而就在这时，天真可爱呆萌傻白甜的川川告诉你，他忘记在柜台里准备零钱了。
你摸了摸口袋，发现自己只带了若干张五角、一元、五元、十元、二十元、五十元、一百元的纸币。现在你想要知道，如何使你买到的生活用品的实用度总和∑vk\sum{v_k}∑vk尽可能大，且需要支付的总金额∑ck\sum{c_k}∑ck又恰好能用你手上的钱支付。注意每种生活用品只能买一次。
第111行一个正整数TTT，表示数据的组数。
对于每一组输入数据，第一行输入a1,a2,...,a7a_1,a_2,...,a_7a1,a2,...,a7，分别表示五毛到一百的纸币的个数。
第二行输入nnn，含义见题目描述。
接下来nnn行，第iii行输入cic_ici，viv_ivi，含义见题目描述。其中，cic_ici为0.50.50.5的正整数倍，viv_ivi为非负整数。保证计算过程不会超出intintint范围。
TTT行，每行一个数，表示能购买的生活用品的最大实用度总和∑vk\sum{v_k}∑vk。如果无法购买任何生活用品，输出−1-1−1。
1 1 1 1 0 1 0 0 5 5 2 10 5 11 10 10.5 1 14 3
17
1 0 0 0 0 0 0 1 4 20 1000 233 2333 377 40 89 12
-1
