Phép cuốn số

Submit solution
Points: 3 (partial)
Time limit: 1.0s
Memory limit: 98M
Author:
TICHPX
Problem type
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG

Cho một số tự nhiên n nếu n có nhiều hơn 1 chữ số mà thỏa mãn chữ số đầu tiên và chữ số cuối cùng có tổng không vượt quá 9 thì có thể rút gọn lại bằng cách bỏ đi chữ số đầu và cộng nó vào chữ số cuối hoặc bỏ đi chữ số cuối rồi cộng vào chữ số đầu

Chẳng hạn \(31425\) thì có thể rút thành \(8142\) hoặc \(1428\)

Nhiệm vụ của bạn là cho một số tự nhiên \(n\) không quá \(10^{18}\) hãy tìm cách rút gọn tối đa số này thế nào để thu được số bé nhất

Input

Một số tự nhiên \(n\) không quá \(10^{18}\)

Output

Giá trị nhỏ nhất của \(n\) sau khi thực hiện các phép rút gọn

Ví dụ

Input

123456

Output

3459

Giải thích Xét số 123456, nếu lấy chữ số đầu cộng chữ số cuối là \(1+6 \leq 9\) có thể rút gọn thành 72345 hoặc 23457 chúng ta chọn cách rút gọn thứ 2 và tiếp tục như sau

\(123456 -> 23457 -> 3459 \)

tichpx

Comments