Số thay thế là số được rút gọn từ số đã cho bằng cách tách các chữ số của số đó, ghi lại chữ số mà tổng các chữ số giống nhau là lớn nhất. Ví dụ: Số 5814 số thay thế là 8; số 1934334 có số thay thế là 39 vì số 9 và số 3 (có 3+3+3) là lớn nhất.

Cho số nguyên không âm ~N~ (~N≤10^6~)

Yêu cầu:

Hãy tìm số thay thế tương ứng với số ~N~ đã cho, các chữ số trong số thay thế được sắp xếp tăng dần.

Dữ liệu vào

Số nguyên không âm ~N~

Kết quả

Số thay thế tương ứng với ~N~

Ví dụ

Input

1934334

Output

39