\(\color{red}{\text{Spoiler Alert}_{{}_{{}^{{}^{v2.0}}}}}\)

\(\color{red}{\text{Khuyến khích bạn đọc trước khi đọc phần lời giải xin hãy thử code ra thuật của mình dù nó có sai hay đúng}}\)

\(\color{red}{\text{Sau đó từ phần bài giải và thuật toán trước đó mà đối chiếu, rút nhận xét với thuật của mình và thu được bài học (không lãng phí thời gian đâu).}}\)

\(\color{orange}{\text{Hint 1 <Brute-force>}}\)

• Thử từng bộ 3 số \((x, y, z)\) thỏa \(x + y + z \leq 1000\) và nếu (\(a * x + b * y + c * z = d\)) thì cập nhật kết quả

\(\color{orange}{\text{Hint 2 <Math>}}\)

• Xét cặp \((x, y)\), ta cần tìm \(z\) để (\(a * x + b * y + c * z = d\))

Dùng toán học, ta tính được \(c * z = d - a * x - b * y\)

Gọi \(S = d - a * x - b * y\)

Nếu \(S \equiv 0 \pmod c\) thì \(z = \frac{S}{c}\) và cập nhật kết quả, ngược lại không tồn tại số nguyên \(z\) thỏa mãn

\(\color{green}{\text{Preference AC Code }}\): Math

\(^{^{\color{purple}{\text{Complexity : }} O((d/min(a, b, c)) ^ 3)\ \color{purple}{\text{time}}\ ||\ O(1)\ \color{purple}{\text{memory}}}}\)

int main()
{
    int a, b, c, d;
    cin >> a >> b >> c >> d;

    int xyz = -1;
    for (int x = 0; x * a <= d; ++x)
    {
        for (int y = 0; x * a + y * b <= d; ++y)
        {
            int left = d - x * a - y * b;
            if (left % c != 0) continue;
            int z = left / c;
            maximize(xyz, x + y + z);
        }
    }

    cout << xyz;
    return 0;
}