import sys # 再帰呼び出しを排除したため setrecursionlimit は不要ですが、 # 念のためインポートは残します。 def main(): # 高速I/O input_data = sys.stdin.read().split() if not input_data: return n_str = input_data[0] length_n = len(n_str) # ターゲットの各桁を数値化（アクセスのたびにint変換しない） target_digits = [int(c) for c in n_str] # DFS用のカウント配列 counts = [0] * 10 # 答えの格納用（リストにして参照書き換え可能にする） best_ans = [None] # ----------------------------------------------------- # 非再帰版: 最小値構築ロジック # ターゲット文字列 target_str 以上で、構成 counts を満たす # 最小の文字列を返す。存在しない場合は None。 # ----------------------------------------------------- def find_smallest_iterative(current_counts, total_digits, target_str, t_digits): # ------------------------------------------------- # ケース1: 桁数がターゲットより多い場合 # -> 最小の非ゼロ数字を先頭にし、残りを昇順に並べる # ------------------------------------------------- if total_digits > len(target_str): for d in range(1, 10): if current_counts[d] > 0: current_counts[d] -= 1 # 文字列構築 res = [str(d)] for k in range(10): c = current_counts[k] if c > 0: res.append(str(k) * c) current_counts[d] += 1 # backtrack (復元) return "".join(res) return None # ------------------------------------------------- # ケース2: 桁数が同じ場合 # -> ターゲットとの共通接頭辞(Prefix)を利用して探索 # ------------------------------------------------- # 戦略: # 1. countsで target の先頭から最大何文字まで一致させられるか(max_p)を調べる。 # 2. 一致長 P = max_p から 0 まで逆順にループする。 # 分岐点 k (0 <= k <= P) において、target[k] より大きい数字 d を # counts から選べるなら、それが「分岐点 k で成立する最小解」である。 # k を大きい方から試すことで、よりターゲットに近い（小さい）値が見つかる。 # 作業用カウント配列 temp_counts = list(current_counts) L = len(target_str) # 1. 最大一致長 max_p を計算 max_p = 0 for val in t_digits: if temp_counts[val] > 0: temp_counts[val] -= 1 max_p += 1 else: break # もし最後まで一致可能なら、それが最小値 (targetそのもの) if max_p == L: return target_str # 2. 分岐点を後ろから探す # temp_counts は現在 max_p 文字分減った状態 # k は「分岐するインデックス」 # k = max_p のときは、prefix一致の後、次の文字で勝負する（実際は不一致で止まった箇所） for k in range(max_p, -1, -1): # ループの初回以外は、一つ後ろの桁(target[k])を「使わなかった」ことにするので在庫に戻す if k < max_p: temp_counts[t_digits[k]] += 1 # 分岐点 k において、target[k] より大きい最小の数字を探す current_digit_val = t_digits[k] found_d = -1 # target[k] + 1 から 9 まで探索 for d in range(current_digit_val + 1, 10): if temp_counts[d] > 0: found_d = d break if found_d != -1: # 見つかった場合、これより上位の桁での分岐より必ず小さくなるので確定 temp_counts[found_d] -= 1 # 結果構築: target[:k] + found_d + 残りを昇順 res = [] # 接頭辞 res.append(target_str[:k]) # 分岐文字 res.append(str(found_d)) # 残り（昇順） for digit in range(10): c = temp_counts[digit] if c > 0: res.append(str(digit) * c) return "".join(res) return None # ----------------------------------------------------- # 整合性チェック関数 (変更なし、計算のみ) # ----------------------------------------------------- def check_and_update(cnt, L): c0, c1, c2, c3, c4, c5, c6, c7, c8, c9 = cnt if (L + c0 + c6 + c8) & 1: return base = (L + c0 + c6 + c8) >> 1 s4 = c0 + c2 + c6 + c8 one = base - s4 if one < 0 or one > c1: return s3 = c0 + c2 + c3 + c5 + c6 + c8 + c9 nine = s3 - base if nine < 0 or nine > c9: return s1 = c0 + c1 + c2 + c3 + c4 + c7 + c8 + c9 zero = s1 - one - base if zero < 0 or zero > c0: return s5 = c0 + c4 + c5 + c6 + c8 + c9 seven = base - (s5 - zero + one) if seven < 0 or seven > c7: return s0 = c0 + c2 + c3 + c5 + c6 + c7 + c8 + c9 six = s0 - zero - base if six < 0 or six > c6: return s6 = c2 + c3 + c4 + c5 + c6 + c8 + c9 if s6 + zero != base: return # 有効なら最小値を構築 candidate = find_smallest_iterative(cnt, L, n_str, target_digits) if candidate is not None: if best_ans[0] is None: best_ans[0] = candidate else: # 文字列長比較 -> 辞書順比較 len_cand = len(candidate) len_best = len(best_ans[0]) if len_cand < len_best: best_ans[0] = candidate elif len_cand == len_best and candidate < best_ans[0]: best_ans[0] = candidate # ----------------------------------------------------- # 非再帰 DFS: スタックを使用 # ----------------------------------------------------- def run_iterative_dfs(total_len): # スタックの要素: [digit_index, current_val, remaining_sum] # digit_index: 現在決めている数字 (0-8) # current_val: counts[digit_index] として試している値 (-1は未処理を示す) # remaining_sum: 残りの割り当て可能数 # 初期状態: 数字0について、まだ値は決めていない(-1)、残り全て(total_len) stack = [[0, -1, total_len]] while stack: frame = stack[-1] d = frame[0] # 直前のループ処理のクリーンアップ（バックトラック） if frame[1] != -1: counts[d] = 0 # 戻す # 次の値を試す frame[1] += 1 val = frame[1] rem = frame[2] # ループ終了条件: 割り当て数が残り数を超えたら pop if val > rem: stack.pop() continue # 値をセット counts[d] = val if d == 8: # 数字8まで決めたら、数字9は残り全てで確定 # ここで再帰の底の処理を行う last_rem = rem - val counts[9] = last_rem check_and_update(counts, total_len) counts[9] = 0 # 8のループを継続するため、ここではpopせず、次のループへ continue else: # 次の深さ(d+1)へ # 新しいフレームをプッシュ stack.append([d + 1, -1, rem - val]) # ----------------------------------------------------- # メインループ # ----------------------------------------------------- # 長さ L を Nの長さ から 20 まで探索 for l in range(length_n, 21): best_ans[0] = None run_iterative_dfs(l) if best_ans[0] is not None: print(best_ans[0]) break if __name__ == '__main__': main()