Notăm X ca fiind mulţimea numerelor naturale care se pot scrie sub forma 2a*3b. Se consideră doar acele numere pentru care 0 ≤ a ≤ D şi 0 ≤ b ≤ T, unde D şi T sunt date. Pentru un număr v din X, considerăm asociatul lui v ca fiind valoarea (C*P)%Q unde C este ultima cifră a lui v iar P şi Q se dau (de exemplu, pentru P = 1 şi Q = 10 asociatul lui 21*32 este 8).

Cerința

Se cere determinarea valorii maxime a sumei asociatelor elementelor unei submulţimi a lui X astfel încât oricare ar fi două elemente u şi v din submulţimea respectivă, u nu divide pe v şi nici v nu divide pe u.

Date de intrare

Fişierul smsm.in conţine pe prima linie patru numere naturale D, T, P şi Q, separate prin câte un spaţiu, reprezentând: puterea maximă la care poate apărea 2 în numerele din X, puterea maximă la care poate apărea 3 în numerele din X, precum şi cele două numere P şi Q, cu semnificaţia descrisă mai sus.

Date de ieșire

Fişierul smsm.out va conţine un singur număr, valoarea maximă a sumei asociatelor elementelor unei submulţimi care se poate forma.

Restricții și precizări

• 1 ≤ D, T, P, Q ≤ 500

Exemplu:

smsm.in

1 1 1 3

smsm.out

2

Explicație

Numerele din mulţimea X sunt: 1 2 3 6. Asociatele lor sunt, respectiv: 1 2 0 0. Putem alege pentru soluţia optimă fie submulţimea {2,3}, fie submulţimea {2}, ambele de sumă a asociatelor 2. Alegând submulţimea {1,2}, cu suma asociatelor 3, nu se respectă constrângerea ca elementele submulţimii să nu se dividă între ele.