It is a little-known story that the young Carl Friedrich Gauss was restless in class, so his teacher came up with a task to keep him preoccupied.
The teacher gave him a series of positive integers . We consider
for
. Additionally, she has given him a set of lucky numbers and the price of each lucky number. If
is a lucky number, then
denotes its price.
Initially, there's a positive integer written on the board. In each move, Carl must make one of the following things:
- If number
is currently written on the board, then Carl can write one of its divisors
, smaller than
, instead of
. If he writes the number
, the price of the move is
, where
is the number of divisors of the positive integer
(including
).
- If
is a lucky number, Carl can leave that number on the board, and the price of the move is
.
Carl must make exactly moves, and after he has made all of his moves, the number
must be written on the board. Let's denote
as the minimal price with which Carl can achieve this.
If it is not possible to make such moves, we define
.
The teacher has given Carl queries. In each query, Carl gets numbers
and
and must calculate the value
, where numbers
are the same for all queries.
Input Specification
The first line of input contains the positive integer
.
The second line contains positive integers
that are less than or equal to
.
The following line contains the positive integer
.
The following line contains positive integers
that are less than or equal to
.
The following line contains the positive integer , the total number of lucky numbers
.
Each of the following lines contains numbers
and
that denote that
is a lucky number, and
is his price
. Each lucky number appears at most once.
The following line contains the positive integer
.
Each of the following lines contains
positive integers
and
.
Output Specification
You must output lines. The
line contains the answer to the
query defined in the task.
Sample Input 1
4
1 1 1 1
2
1 2
2
2 5
4 10
1
4 2
Sample Output 1
7
Explanation for Sample Output 1
, so Carl can make exactly one move - replace number
with number
, so
.
, so Carl has two options:
- He can replace number
with number
and then leave number
(because it's a lucky number), so he pays the price
.
- He can leave number
in the first move, and replace it in the second move with number
, so the price is
.
The first option costs less, so .
The answer to the query is
.
Sample Input 2
3
6 9 4
2
5 7
3
1 1
7 8
6 10
2
6 2
70 68
Sample Output 2
118
-2
Sample Input 3
3
8 3 10
2
8 4
3
1 6
5 1
3 7
2
5 1
3 1
Sample Output 3
16
66
Comments