星际跃迁的稳定信标

import java.util.*;
import java.io.*;

// 构造各位递增的数字, 不超过Fmax, 检查各位和质数
// 数位DP：简单应用, 当然普通回溯也行
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        char[] nums = br.readLine().toCharArray();
        sieve();
        System.out.println(dfs(0, 0, 0, 0, true, nums));
    }

    // 数位DP
    static long dfs(long x, int sum, int pre, int i, boolean isLimit, char[] nums) {
        if (i == nums.length) {
            return prime[sum] ? x : -1;
        }

        long res = -1;
        int upper = isLimit ? nums[i] - '0' : 9;
        for (int k = pre; k <= upper; k++) {
            res = Math.max(res, dfs(x * 10 + k, sum + k, k, i + 1, isLimit && k == upper, nums));
        }
        return res;
    }

    // 质数筛选
    static final boolean[] prime = new boolean[163];
    static void sieve() {
        Arrays.fill(prime, true);
        prime[0] = prime[1] = false;
        for (int i = 2; i <= 13; i++) {
            if (prime[i]) {
                for (int j = i + i; j <= 162; j += i) {
                    prime[j] = false;
                }
            }
        }
    }
}