toys

Dupa ce a dat o petrecere la el acasa, Gigel impreuna cu colegii sai de gradinita trebuie sa duca toate jucariile din sufragerie la el in camera. Pentru a ajunge din sufragerie in camera lui Gigel, copiii trebuie sa strabata un hol de lungime L.
Gigel are N prieteni (pe care i-a numerotat de la 1 la N) si mai are de mutat M jucarii. Prietenii sai au inceput deja treaba si se gasesc undeva intre sufragerie si camera lui Gigel. Unii dintre ei au deja o jucarie de transportat, ceilalti se intorc in sufragerie pentru a lua o noua jucarie.
Vom identifica pozitia de pe hol a unui copil prin distanta la care se afla copilul de camera lui Gigel. Mai exact, pentru fiecare copil i vom determina doua valori d_i si t_i, cu semnificatia: d_i reprezinta distanta la care se afla fata de camera lui Gigel copilul i, iar t_i=1, in cazul in care copilul i transporta o jucarie din sufragerie spre camera lui Gigel, respectiv t_i=0 in cazul in care copilul i se intoarce din camera lui Gigel catre sufragerie, fara nici o jucarie.
Fiecare copil duce o jucarie in camera lui Gigel, apoi se intoarce in sufragerie pentru a lua o noua jucarie repetand acest proces pana cand toate jucariile vor fi transportate.
Gigel analizeaza configuratia celor N prieteni si observa ca d₁=S si t₁=1 (adica primul copil se afla la distanta S de camera lui Gigel si transporta o jucarie). Pentru ceilalti copii (i=2, 3, ..., N) valorile d_i si t_i se pot determina cu urmatoarele formule (in care valorile X, Y, Z, V sunt cunoscute):
d_i = ( X * d_i-1 + Y * ( i - 1 ) ) % ( L - 1 ) + 1
t_i = ( Z * d_i-1 + V * ( i - 1 ) ) % 2
Prin a % b se intelege restul impartirii lui a la b.

Cerinta

Ajutati-l pe Gigel sa determine timpul minim in care toate jucariile vor fi duse inapoi in camera sa.

Date de intrare

Pe prima linie a fisierului de intrare toys.in sunt scrise trei numere naturale: N, L si M separate prin cate un spatiu. Pe urmatoarea linie se afla cinci numere naturale S,X,Y,Z,V separate prin cate un spatiu, avand semnificatia din enunt.

Date de iesire

Fisierul toys.out va contine o singura linie pe care va fi scris timpul minim in care toate jucariile vor fi transportate in camera lui Gigel.

• 1 <= M <= 2 000 000 000
• 0 <= N <= 2 000 000
• 0 <= L <= 2 000 000
• 0 <= X, Y, Z, V <= 2 000 000
• 0 <= S <= L
• Rezultatul se va incadra in tipuri de date intregi pe 64 de biti.
• Copiii se deplaseaza o unitate de distanta intr-o unitate de timp, iar lasatul sau luatul unei jucarii nu consuma timp.

  Timp maxim de executie/test: 0.2 secunde

Diaconu Adrian Paul
Universitatea Bucuresti, Facultatea de Matematica si Informatica
ditzone@gmail.com