### Problem Statement

You are given the following equation:

A * x + B * y + C * z = W

where x, y and z are integers greater than or equal to 0. Return the minimal possible sum x + y + z, or -1 if a solution does not exist.

### Definition

 Class: SolvingEquation Method: solve Parameters: int, int, int, int Returns: int Method signature: int solve(int A, int B, int C, int W) (be sure your method is public)

### Constraints

-A, B, C and W will each be between 1 and 100, inclusive.

### Examples

0)

 `1` `2` `3` `5`
`Returns: 2`
 The solution that minimizes x + y + z is x = 0, y = 1 and z = 1. 1*0 + 2*1 + 3*1 = 5. The return value is x + y + z = 0 + 1 + 1 = 2.
1)

 `1` `2` `3` `10`
`Returns: 4`
 The best solution here is x = 1, y = 0 and z = 3.
2)

 `3` `3` `5` `7`
`Returns: -1`
 There is no solution for the equation 3*x + 3*y + 5*z = 7.
3)

 `1` `1` `1` `100`
`Returns: 100`
4)

 `1` `10` `20` `99`
`Returns: 14`
5)

 `100` `100` `1` `1`
`Returns: 1`

#### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=8141

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10799&pm=8141

Relja

#### Testers:

PabloGilberto , brett1479 , Olexiy , ivan_metelsky

#### Problem categories:

Simple Search, Iteration