\(\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>}}\)

• Chọn tất cả các khoảng 3 đoạn và kiểm tra nếu thỏa thì chọn số lớn nhất

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

• Có thể tiền xử lí trước tổng của từng đoạn

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

• Lúc kiểm tra chúng ta có thể biến đổi toán học

\(a ^ 2 + b ^ 2 = c ^ 2 \Leftrightarrow a ^ 2 = (c - b) \times (c + b) \Leftrightarrow \frac{a}{c + b} = \frac{c - b}{a}\)

Thay vì nhân thì ta có thể chia, và thay vì chia thì ta có thể đưa về phân số tối giản để kiểm tra chuẩn xác hơn

\(\color{orange}{\text{Hint 4 <Branch-and-bound>}}\)

• Trước khi kiểm tra ta sắp xếp lại 3 số

• Vì vị trí là không còn quan trọng ta có thể chỉ cần duyệt hai đoạn và biết được đoạn còn lại

• Với giới hạn đề bài ta chỉ cần duyệt 18 chữ số là cùng

\(\color{green}{\text{Preference AC Code }}\): Branch-and-bound, Precalculation, Math

\(^{^{\color{purple}{\text{Complexity : }} O(n ^ 2 \log(max\_val))\ \color{purple}{\text{time}}\ ||\ O(n ^ 2)\ \color{purple}{\text{memory}}}}\)

/// a ^ 2 + b ^ 2 = c ^ 2
/// a / (c + b) = (c - b) / a
bool check(ll a, ll b, ll c)
{   
    ll t = c + b;
    ll h = c - b;
    ll f1 = gcd(a, t);
    ll f2 = gcd(h, a);
    return (a / f1 == h / f2) && (t / f1 == a / f2);
}

void sort3(ll &a, ll &b, ll &c)
{
    if (a > b) swap(a, b);
    if (a > c) swap(a, c);
    if (b > c) swap(b, c);
}

int main()
{
    string s;
    cin >> s;
    int n = s.size();

    vector<int> d(n + 1, 0);
    for (int i = 1; i <= n; ++i)
        d[i] = s[i - 1] - '0';

    vector<vector<ll> > f(n + 1, vll(n + 1, 0));
    for (int l = 1; l <= n; ++l)
    {
        ll num = 0;
        for (int r = l, upr = min(l + 18, n); r <= upr; ++r)
        {
            num = 10LL * num + d[r];
            f[l][r] = num;
        }
    }

    ll res = 0;
    for (int x = 1, upx = min(18, n - 2); x <= upx; ++x)
    {
        for (int y = x + 1, upy = min(18 + x, n - 1); y <= upy; ++y)
        {
            ll a = f[1][x - 1];
            ll b = f[x][y - 1];
            ll c = f[y][n];
            sort3(a, b, c);
            if (check(a, b, c))
                maximize(res, c);
        }
    }
    cout << res;
    return 0;
}