1216 : Container Orders

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

Source