Sealing up

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
January and February are usually very cold in ChefLand. The temperature may reach 20 and even 30 degrees Celsius. Because of that, many people seal up windows in their houses.
Sergey also lives in ChefLand. He wants to seal the window in his house. The window has the shape of a simple convex polygon with N vertices.
For the sealing, there are M kinds of sticky stripes, which are sold in the shops. The stripe of the i^{th} type has the length of L_{i} millimeters and the cost of C_{i} rubles.
The sealing process consists in picking the stripe and sticking it on the border of the window. The stripe can't be cut (it is made of very lasting material) and can only be put straight, without foldings. It is not necessary to put the strip strictly on the window border, it can possibly extend outside the border side of window too (by any possible amount). The window is considered sealed up if every point on its' border is covered with at least one stripe.
Now Sergey is curious about the stripes he needs to buy. He wonders about the cheapest cost, at which he can seal his window. Please help him.
Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains a single integer N denoting the number of number of vertices in the polygon denoting Sergey's window.
Each of the following N lines contains a pair of spaceseparated integer numbers X_{i} Y_{i}, denoting the coordinates of the i^{th} points.
The following line contains a single integer M denoting the number of types of sticky stripe which is sold in the shop.
Each of the following M lines contains a pair of spaceseparated integers L_{i} C_{i} denoting the length and the cost of the sticky stripe of the i^{th} type respectively.
Output
For each test case, output a single line containing the minimum cost of sealing up the window.
Constraints
 1 ≤ T ≤ 10
 The coordinates of the window are given either in clockwise or in a counterclockwise order.
 No three or more vertices lie on the same line (i.e. are collinear).
 0 ≤ X_{i}, Y_{i} ≤ 10^{6}
 1 ≤ L_{i}, C_{i} ≤ 10^{6}
Subtasks
 Subtask #1 (17 points): 3 ≤ N ≤ 10, M = 1
 Subtask #2 (24 points): 3 ≤ N ≤ 42, M ≤ 2
 Subtask #3 (59 points): 3 ≤ N ≤ 2000, 1 ≤ M ≤ 10
Example
Input: 1 4 0 0 1000 0 1000 2000 0 2000 2 1000 10 2000 15 Output: 50
Explanation
Example case 1. In this case, Sergey's window is a rectangle with the side lengths of 1000 and 2000. There are two types of the sticky stripes in the shop  the one of the length 1000 with the cost of 10 rubles and with the length of 2000 and the cost of 15 rubles. The optimal solution would be to buy 2 stripes of the first type 2 stripes of the second type. The cost will be 2 × 15 + 2 × 10 = 50 rubles.
Author:  xcwgf666 
Tester:  errichto 
Editorial  https://discuss.codechef.com/problems/SEALUP 
Tags  dynamicprogramming, easy, geometry, ltime44, xcwgf666 
Date Added:  10012017 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, PYP3, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 