{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e\r\n\t\u003cspan lang\u003d\"EN-US\"\u003eThere is a \u003cspan data-scayt_word\u003d\"SuperSale\" data-scaytid\u003d\"2\"\u003eSuperSale\u003c/span\u003e in a \u003cspan data-scayt_word\u003d\"SuperHiperMarket\" data-scaytid\u003d\"5\"\u003eSuperHiperMarket\u003c/span\u003e. Every person can take only one object of each kind, i.e. one TV, one carrot, but for extra low price. We are going with a whole family to that \u003cspan data-scayt_word\u003d\"SuperHiperMarket\" data-scaytid\u003d\"6\"\u003eSuperHiperMarket\u003c/span\u003e. Every person can take as many objects, as he/she can carry out from the \u003cspan data-scayt_word\u003d\"SuperSale\" data-scaytid\u003d\"3\"\u003eSuperSale\u003c/span\u003e. We have given list of objects with prices and their weight. We also know, what is the maximum weight that every person can stand. What is the maximal value of objects we can buy at \u003cspan data-scayt_word\u003d\"SuperSale\" data-scaytid\u003d\"4\"\u003eSuperSale\u003c/span\u003e?\u003c/span\u003e\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003e\r\n\tThe input consists of\u0026nbsp;\u003cvar\u003eT\u003c/var\u003e\u0026nbsp;test cases. The number of them (1\u0026lt;\u003d\u003cvar\u003eT\u0026lt;\u003d1000\u003c/var\u003e) is given on the first line of the input file.\u003c/p\u003e\r\n\u003cp\u003e\r\n\tEach test case begins with a line containing a\u0026nbsp;single integer number\u0026nbsp;\u003cvar\u003eN\u0026nbsp;\u003c/var\u003ethat indicates the number of objects (\u003cvar\u003e1 \u0026lt;\u003d N \u0026lt;\u003d 1000\u003c/var\u003e). Then follows\u0026nbsp;\u003cem\u003eN\u003c/em\u003e\u0026nbsp;lines, each containing two integers: P and W. The first integer (1\u0026lt;\u003dP\u0026lt;\u003d100) corresponds to the price of object. The second\u0026nbsp;\u0026nbsp;integer (1\u0026lt;\u003dW\u0026lt;\u003d30) corresponds to the weight of object. Next line contains one integer (1\u0026lt;\u003dG\u0026lt;\u003d100)\u0026nbsp;\u0026nbsp;it\u0026rsquo;s the number of people in our group. Next G lines contains maximal weight (1\u0026lt;\u003dMW\u0026lt;\u003d30) that can stand this \u003cspan data-scayt_word\u003d\"i-th\" data-scaytid\u003d\"8\"\u003ei\u003cem\u003e\u003cspan data-scayt_word\u003d\"-th\" data-scaytid\u003d\"1\"\u003e-th\u003c/span\u003e\u003c/em\u003e\u003c/span\u003e\u0026nbsp;person from our family (1\u0026lt;\u003di\u0026lt;\u003dG).\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003e\r\n\tFor every test case your program has to determine one integer. Print out the maximal value of goods which we can buy with that family.\u003c/p\u003e"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cpre\u003e\r\n2\r\n3\r\n72 17\r\n44 23\r\n31 24\r\n1\r\n26\r\n6\r\n64 26\r\n85 22\r\n52 4\r\n99 18\r\n39 13\r\n54 9\r\n4\r\n23\r\n20\r\n20\r\n26\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cpre\u003e\r\n72\r\n514\u003c/pre\u003e"}}]}