Minimum Bottles Problem

Given three integers \(W\), \(X\), and \(Y\), determine the minimum number of bottles required to exactly measure \(W\) liters of water. There are two types of bottles available with capacities \(X\) liters and \(Y\) liters, respectively. You can use any combination of these bottles as long as the total volume is exactly \(W\) liters. If it is impossible to measure exactly \(W\) liters, output \(-1\).

The problem can be formally stated as follows. Find non-negative integers \(i\) and \(j\) such that:

\(i \times X + j \times Y = W\)

and minimize \(i+j\). A necessary condition for a solution to exist is that \(W\) is a multiple of \(\gcd(X, Y)\). Use this insight to solve the problem efficiently.

inputFormat

The input consists of a single line containing three space-separated integers: \(W\) (the required water in liters), \(X\) (capacity of the first type of bottle), and \(Y\) (capacity of the second type of bottle).

outputFormat

Output a single integer representing the minimum number of bottles required to measure exactly \(W\) liters of water. If it is not possible to measure \(W\) liters using the given bottle sizes, output \(-1\).

10 3 5

2