Minimum Cost Division Game

Given integers (F(1),F(2),\ldots,F(K)) (with (F(i)=0) for (i>K)), (T) lucky integers (X_i) along with their prices (C(X_i)), and (M) integers (L_1,L_2,\ldots,L_M). Initially, a blackboard contains an integer (A). You can perform exactly one of the following two operations per move:

1. Suppose the current number is (N). You may choose any proper divisor (M) of (N) (i.e. (M) is a factor of (N) with (M < N)) and write (M) on the board. The cost incurred is (F\bigl(d(N\div M)\bigr)), where the function (d(x)) denotes the number of positive divisors of (x) (including (x) itself). Note that if (d(N\div M)>K), then (F\bigl(d(N\div M)\bigr)=0).

2. If (N) is one of the lucky integers (i.e. it appears in ({X_i})), you can choose to leave (N) unchanged on the board at a cost of (C(N)).

For any two integers (A) and (B) and for a given number of moves (L), let (G(A,B,L)) be the minimum total cost to transform (A) into (B) in exactly (L) moves. Your task is to compute [ S = G(A,B,L_1) + G(A,B,L_2) + \cdots + G(A,B,L_M). ]

It is guaranteed that (B) is reachable from (A) under the given operations. All formulas are in (\LaTeX) format.

inputFormat

The first line contains three integers: K, T and M.

The second line contains K integers: F(1) F(2) ... F(K).

The next T lines each contain two integers: X and C(X), representing a lucky integer and its cost.

The next line contains M integers: L1 L2 ... LM.

The last line contains two integers: A and B.

outputFormat

Output a single integer, the value of \(S = G(A,B,L_1)+G(A,B,L_2)+...+G(A,B,L_M)\).

sample

3 2 2
1 2 3
2 5
3 6
1 2
6 1

4