CSG-CPC
Online Judge

1216 : Container Orders

         Time Limit: 1 Sec     Memory Limit: 128 Mb     Submitted: 1     Solved: 1    

Description

binarycopycode research in using Deep Reinforcement Learning(DRL) to solve Container Relocation Problem(CRP) during his master degree. Now he want to ask you one question about containers orders. Of course not about DRL.

There are \(n\) containers, where the \(i^{th}\) container has a weight of \(2^{k_i}\) and an associated cost value of \(W_i\).

Here comes \(m\) orders, each specifying a desired combination of containers whose total weight should exactly equal \(h_j*2^{t_j}\). Our objective is to determine the minimum cost required to fulfill all of these orders.

Input

First line, one integer \(n(1 \leq n \leq 10,000)\) .

next \(n\) lines, \(k_i(0 \leq k_i \leq 1,000)\) and \(W_i(0 \leq W_i \leq 10,000)\).

next one line, one integer \(m(1 \leq m \leq 10,000)\).

next \(m\) lines, two integer \(t_j(0\leq t\leq 1,000)\) and \(h_j(0 \leq h,\sum{h}\leq5,000)\).

Output

one line, the minimum cost. If it is impossible to fulfill all the orders, output “-1”.

Sample

1
10 0
1
9 2
0

Hint