smsm

Notăm $X$ ca fiind mulţimea numerelor naturale care se pot scrie sub forma $2^a \cdot 3^b$. Se consideră doar acele numere pentru care $0 \leq a \leq D$ şi $0 \leq b \leq T$, unde $D$ şi $T$ sunt date. Pentru un număr $v$ din $X$, considerăm asociatul lui $v$ ca fiind valoarea $(C \cdot 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 $2 \cdot 3^2$ este $8$).

Cerinţă

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 \leq D, T, P, Q \leq 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, 1 \}$, cu suma asociatelor $3$, nu se respectă constrângerea ca elementele submulţimii să nu se dividă între ele.