Xin cảm ơn DevGang đã cung cấp bộ đề, test và lời giải cho bài này.

Một số nguyên dương được gọi là số Niven (hoặc số Harshad) nếu nó chia hết cho tổng các chữ số của nó. Một số được gọi là số Niven cân bằng nếu số đó là số Niven và có số lượng chữ số chẵn bằng số lượng chữ số lẻ. Ví dụ: $10, 12, 45$ là các số Niven cân bằng, còn $14, 25, 28$ không là các số Niven cân bằng.

Yêu cầu: Cho một số nguyên dương $n$, em hãy tìm số Niven cân bằng lớn nhất nhỏ hơn hoặc bằng $n$. ($10\le n\le10^{6}$).

Dữ liệu vào

Đọc từ file văn bản NUM.INP gồm một số nguyên dương $n$.

Kết quả ra

Ghi ra file văn bản NUM.OUT một số nguyên là đáp án của bài toán.

Ràng buộc

• Có 50% test với $10 \le n \le 10^{3}$.

• Có 50% test với $10^{3} < n \le 10^{6}$.

Ví dụ

Dữ liệu 1

1212

Kết quả 1

1212

Giải thích 1

Với $n=1212$ ta có số ~1212~ là số Niven cân bằng lớn nhất nhỏ hơn hoặc bằng $n$ vì số ~1212~ có ~2~ chữ số lẻ và ~2~ chữ số chẵn, đồng thời tổng các chữ số là ~6~ nên ~1212~ chia hết cho ~6~.

Dữ liệu 2

51

Kết quả 2

50