ami có 4 số nguyên dương \(a , b , c , d\). Các bạn cần giải phương trình sau \(a * x + b * y + c * z = d\). Đây là phương trình cơ bản có thể giải bằng thuật toán Euclid mở rộng. Để làm bài toán khó hơn, các bạn cần tìm các số \(x, y, z\) là các số nguyên KHÔNG ÂM thoả phương trình trên vào tổng \(x + y + z\) là lớn nhất.

Input

• 1 dòng chứa 4 số nguyên dương \(a , b , c , d\).

Output

• In ra \(1\) dòng là tổng lớn nhất của một nguyên không âm. Nếu không có nghiệm in ra \(-1\)

Scoring

• Subtask \(1\) (\(90\%\) số điểm): \(a , c , b \leq 100, d \leq 1000\), và đáp án \(x + y + z \leq 100\).

• Subtask \(2\) (\(10\%\) số điểm): \(b , c , a \leq 1000, d \leq 1000\), và đáp án \(x + y + z \leq 1000\).

Example

1 2 3 6 

6