Balanced Sweet Purchase

Every day, Danny buys a single sweet from a candy store offering \(m\) types of sweets (numbered from 1 to \(m\)). For each type \(i\), he has set a target fraction \(f_i\) (with \(0 < f_i \le 1\)) so that after he has eaten a total of \(n\) sweets – with \(s_i\) sweets of type \(i\) – the following balanced condition holds for every \(1 \le i \le m\):

\( n \cdot f_i - 1 < s_i < n \cdot f_i + 1 \)

Danny’s eating history (the sequence of purchased sweets) has satisfied this property so far. Now he wonders how many more sweets he can buy (one at a time) so that after every additional purchase the collection remains balanced. If he can continue buying sweets forever without breaking the condition, output -1.

inputFormat

The input consists of four parts:

1. An integer \(m\) on the first line indicating the number of sweet types.
2. The second line contains \(m\) real numbers \(f_1, f_2, \dots, f_m\) (the target fractions). It is guaranteed that \(\sum_{i=1}^{m} f_i = 1\).
3. An integer \(n\) on the third line representing the number of sweets eaten so far.
4. The fourth line contains \(n\) integers \(a_1, a_2, \dots, a_n\) (each between 1 and \(m\)) representing the types of sweets Danny has eaten in order. It is guaranteed this initial sequence is balanced.

outputFormat

Output a single integer: the maximum number of additional sweets Danny can buy while preserving the balanced condition after each purchase. If Danny can purchase sweets indefinitely without breaking the balance, output -1.

sample

2
0.5 0.5
2
1 2

2