Tenu

Cerință

David trebuie să îşi plătească comanda de pe Tenu. Acesta a comandat $a$ produse identice, fiecare având prețul $b$. Din păcate, el are doar bancnote cu valoarea de forma $5^k$. Ştiind numerele $a$ și $b$, numere naturale de $n$, respectiv $m$ cifre, şi numărul $k$, să se afle restul pe care curierul i-l datorează lui David, presupunând că acesta plătește suma minimă necesară astfel încât să-și achite comanda.

Date de intrare

Pe prima linie se găsesc numerele $n$, $m$ și $k$ cu semnficaţia din enunţ.
Pe cea de-a doua linie se găsesc $n$ cifre separate prin spațiu, reprezentând numărul $a$.
Pe cea de-a treia linie se găsesc $m$ cifre separate prin spațiu, reprezentând numărul $b$.

Date de ieșire

Pe prima linie se va găsi un singur număr întreg, reprezentând restul pe care David trebuie să îl primească.

Restricții și precizări

• $1 \leq k \leq 12$;
• $1 \leq n, m \leq 100 \ 000$;
• Problema diferă față de cea din concurs, având valoarea bancnotelor de forma $5^k$ în loc de $2^k$. Am făcut această modificare pentru a realiza punctarea soluțiilor în modul în care ne-am fi dorit.
• Pentru citirea și afișarea rapidă, se recomandă folosirea acestor linii de cod la începutul funcției main:

ios::sync_with_stdio(false);  
cin.tie(NULL);  
cout.tie(NULL);  

Exemplul 1

stdin

2 3 2
3 0
1 3 5

stdout

0

Explicație

David va avea de plătit suma totală de $30 \cdot 135 = 4050$. Acesta are doar bancnote cu valoarea $5^2 = 25$, deci poate plăti suma fixă, fără să fie nevoie să primească rest.

Exemplul 2

stdin

7 8 3
7 6 2 0 5 7 5
6 8 6 7 6 7 5 4

stdout

75

Explicație

David va avea de plătit suma totală de $7 \ 620 \ 575 \cdot 68 \ 676 \ 754 = 523 \ 356 \ 354 \ 613 \ 550$, cu bancnote de valoare $5^3 = 125$, deci va trebui să primească restul $75$.

Exemplul 3

stdin

18 17 9
4 2 2 2 6 1 0 0 3 3 1 0 1 4 2 2 3 5 
9 1 0 5 8 0 9 6 4 8 1 5 1 3 2 1 6 

stdout

1862865