Now You-know-who loves recurrence relations and second order recurrence in particular.
He-who-must-not-be-named defines:
F(n) = a*F(n-1)+b*F(n-2) , n>1
Where
F(0) and
F(1) are already known to him.
This time he is annoyed because Harry was successful in breaking the password last time. So he has decided to change the password for his last horcrux.
Now Harry will be given two
0-indexed arrays A and B of size
N.
He-who-must-not-be-named defines
He set the password for his vault as
Once again Harry is not able to decrypt the password and seeks for your help.
Input format:
First line of input contains five space separated integer
N,a,b,F(0) and
F(1).
Second line of input contains
N space separated integers denoting the value of
A0,A1,...An-1.
Third line of input contains
N space separated integers denoting the value of
B0,B1,...Bn-1.
Output format:
Single integer denoting the value of password.
Constraints:
0 < N,a,b,F(0),F(1) < 1e5
0 <= A_i , B_i < 1e9
Sample Input:
5 4 2 1 4
9 7 4 4 13
19 12 10 14 3
Sample Output:
810
