Farmer John nhận đơn đặt đúng $M$ đơn vị sữa ($1 \leq M \leq 1,000$) cần hoàn thành ngay. Không may máy vắt sữa hiện đại vừa hỏng và ông chỉ có ba xô dung tích nguyên $X$, $Y$ và $M$ ($1 \leq X < Y < M$), ban đầu đều rỗng. Ông có thể thực hiện tùy ý số lần hai thao tác:
- Đổ đầy xô nhỏ dung tích $X$ bằng $X$ đơn vị sữa rồi rót vào xô dung tích $M$, miễn không làm xô dung tích $M$ tràn.
- Đổ đầy xô vừa dung tích $Y$ bằng $Y$ đơn vị sữa rồi rót vào xô dung tích $M$, miễn không làm xô dung tích $M$ tràn.
FJ biết có thể không đổ đầy xô dung tích $M$. Hãy giúp ông xác định lượng sữa lớn nhất có thể thêm vào xô này.
Dữ liệu vào
Dòng duy nhất chứa $X$, $Y$ và $M$, cách nhau bởi dấu cách.
Dữ liệu ra
In lượng sữa lớn nhất FJ có thể thêm vào xô dung tích $M$.
Ví dụ
Dữ liệu vào 1
17 25 77
Dữ liệu ra 1
76
Ghi chú
FJ đổ đầy xô dung tích 17 ba lần và xô dung tích 25 một lần, tổng cộng 76 đơn vị sữa.
Tác giả: Brian Dean