Farmer John קיבל הזמנה של בדיוק $M$ יחידות חלב ($1 \leq M \leq 1,000$) שיש לספק מיד. אך מכונת החליבה המשוכללת התקלקלה, ונשארו רק שלושה דליים בעלי קיבולות שלמות $X$, $Y$ ו-$M$ ($1 \leq X < Y < M$), כולם ריקים בהתחלה. אפשר לבצע כל מספר של פעולות משני הסוגים:
- למלא את הדלי הקטן, בקיבולת $X$, עד שפתו ב-$X$ יחידות חלב ולשפוך לדלי בקיבולת $M$, בתנאי שהדלי בקיבולת $M$ לא יגלוש.
- למלא את הדלי הבינוני, בקיבולת $Y$, עד שפתו ב-$Y$ יחידות חלב ולשפוך לדלי בקיבולת $M$, בתנאי שהדלי בקיבולת $M$ לא יגלוש.
FJ יודע שאולי אי אפשר למלא לגמרי את הדלי בקיבולת $M$. עזרו לקבוע את כמות החלב המרבית שאפשר להוסיף אליו.
קלט
בשורה היחידה $X$, $Y$ ו-$M$, מופרדים ברווחים.
פלט
הדפיסו את כמות החלב המרבית ש-FJ יכול להוסיף לדלי בקיבולת $M$.
דוגמאות
קלט 1
17 25 77
פלט 1
76
הערה
FJ ממלא את הדלי בקיבולת 17 שלוש פעמים ואת הדלי בקיבולת 25 פעם אחת, וצובר 76 יחידות חלב.
מחבר: Brian Dean