Farmer John a reçu une commande d'exactement $M$ unités de lait ($1 \leq M \leq 1,000$) à fournir immédiatement. Sa machine à traire sophistiquée vient de tomber en panne, et il ne reste que trois seaux de capacités entières $X$, $Y$ et $M$ ($1 \leq X < Y < M$), tous initialement vides. Il peut effectuer autant d'opérations des deux types suivants qu'il le veut :

• Remplir le petit seau de capacité $X$ avec $X$ unités de lait et le verser dans celui de capacité $M$, à condition que le seau de capacité $M$ ne déborde pas.
• Remplir le seau moyen de capacité $Y$ avec $Y$ unités de lait et le verser dans celui de capacité $M$, à condition que le seau de capacité $M$ ne déborde pas.

FJ sait qu'il ne pourra peut-être pas remplir entièrement le seau de capacité $M$. Aidez-le à déterminer le maximum de lait qu'il peut y ajouter.

Entrée

L'unique ligne contient $X$, $Y$ et $M$, séparés par des espaces.

Sortie

Affichez le maximum de lait que FJ peut ajouter au seau de capacité $M$.

Exemples

Entrée 1

17 25 77

Sortie 1

76

Remarque

FJ remplit trois fois le seau de capacité 17 et une fois celui de capacité 25, pour 76 unités de lait.

Auteur : Brian Dean