토끼의 전설

'궁수의 전설'을 즐기는 수학토끼는 '궁수의 전설'을 패러디한 게임인 '토끼의 전설'을 만들었다. 이 게임에는 특이한 캐릭터 업그레이드 시스템이 고안되어 있다.

• 각 캐릭터는 기본 체력과 공격력을 가지고 있고, 마법 주문서를 통해 그 값을 더 증가시킬 수 있다.
• 마법 주문서는 $N$종류가 존재하며, $i$번 마법 주문서의 체력 증가량과 공격력 증가량은 각각 $c_i$와 $p_i$이다.
• 각 마법 주문서는 한 캐릭터에게 최대 한 번만 사용 가능하다.
• $i$번 마법 주문서의 가격은 $i$번 마법 주문서의 공격력 증가량 $p_i$와 같다.

수학토끼는 마법 주문서의 밸런스를 맞추기 위해 공격력이 체력의 $x$배 이상이 되게 하기 위한 최소 비용을 알아내고 싶다. $Q$개의 캐릭터의 기본 체력 $C$와 기본 공격력 $P$가 주어질 때마다, $N$개의 주문서 중 일부를 활용해 공격력이 체력의 $x$배 이상이 되도록 만들 수 있는지 판별하고, 그것이 가능한 경우 최소 비용을 출력하라. (주문서를 하나도 활용하지 않아도 되고, 주문서를 모두 활용해도 된다.)

엄밀히 말하면, $Q$개의 $(C, P)$ 쌍이 주어질 때마다 다음을 만족시키는 집합 $S \subseteq \{1, 2, \cdots, N\}$들에 대해 가능한 $\sum_{i \in S} {p_i}$의 최솟값을 출력하면 된다.

$$ \frac{P + \sum_{i \in S} p_i}{C + \sum_{i \in S} c_i} \geq x $$

첫 번째 줄에 마법 주문서의 종류의 수 $N$이 주어진다.

두 번째 줄에 $N$개의 정수 $c_1, c_2, \cdots, c_N$가 공백으로 구분되어 주어진다.

세 번째 줄에 $N$개의 정수 $p_1, p_2, \cdots, p_N$가 공백으로 구분되어 주어진다.

네 번째 줄에 $x = \frac{a}{b}$의 분자 $a$와 분모 $b$가 공백으로 구분되어 주어진다.

다섯 번째 줄에 캐릭터의 개수 $Q$가 주어진다.

이후 $Q$개의 줄 중 $j$번째 줄에 $j$번째 캐릭터의 $C$와 $P$의 값이 공백으로 구분되어 주어진다. $(1 \leq j \leq Q)$

각 캐릭터에 대한 최소 비용을 $Q$개의 줄에 걸쳐 한 줄에 하나씩 출력한다. 만약 불가능한 경우 -1을 출력한다.

• $1 \leq N \leq 500$
• $1 \leq c_i \leq 500 ~ (1 \leq i \leq N)$
• $1 \leq p_i \leq 500 ~ (1 \leq i \leq N)$
• $1 \leq a, b \leq 10^9$
• $1 \leq Q \leq 10^5$
• $1 \leq C, P \leq 500$