题目描述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

来源Source