Tiền Dễ Dàng

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Xem hướng dẫn
Tác giả:
ami
Dạng bài
Điểm: 100 (p) Thời gian: 2.0s Bộ nhớ: 257M Input: bàn phím Output: màn hình

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

Test 1

Input 
1 2 3 6
Output 
6
Note

Chọn \(x = 6, y = 0 , z = 0\), ta có \(6 * 1 + 0 + 0 = 6\).

Bình luận