here is the C# code using System; using System.Collections.Generic; using System.Linq;

class Program { // Cache for concatenated prime checks. static Dictionary primeCache = new Dictionary();

static void Main()
{
    // Read input: N and K separated by a space.
    string[] tokens = Console.ReadLine().Split();
    int N = int.Parse(tokens[0]);
    int K = int.Parse(tokens[1]);

    // Generate all primes less than N.
    List<int> primes = SievePrimes(N);
    int nprimes = primes.Count;

    // Precompute 10^(number of digits) for each prime.
    int[] pow10 = new int[nprimes];
    for (int i = 0; i < nprimes; i++)
    {
        int digits = primes[i].ToString().Length;
        pow10[i] = (int)Math.Pow(10, digits);
    }

    // Build compatibility lists: for each prime (index i), comp[i] holds indices j (with j > i)
    // such that both concatenations (primes[i] followed by primes[j] and vice-versa) are prime.
    List<int>[] comp = new List<int>[nprimes];
    for (int i = 0; i < nprimes; i++)
        comp[i] = new List<int>();

    for (int i = 0; i < nprimes; i++)
    {
        for (int j = i + 1; j < nprimes; j++)
        {
            int concat1 = primes[i] * pow10[j] + primes[j];
            int concat2 = primes[j] * pow10[i] + primes[i];
            if (IsConcatPrime(concat1) && IsConcatPrime(concat2))
                comp[i].Add(j);
        }
    }

    // Build HashSet versions for fast candidate intersection.
    HashSet<int>[] compHS = new HashSet<int>[nprimes];
    for (int i = 0; i < nprimes; i++)
        compHS[i] = new HashSet<int>(comp[i]);

    List<int> currentSet = new List<int>();
    List<int> sums = new List<int>();

    // Try each prime as a starting point.
    for (int i = 0; i < nprimes; i++)
    {
        currentSet.Add(i);
        List<int> candidates = new List<int>(comp[i]);
        Search(comp, compHS, primes, currentSet, candidates, K, sums);
        currentSet.RemoveAt(currentSet.Count - 1);
    }

    // Sort and print the resulting sums.
    sums.Sort();
    foreach (var s in sums)
        Console.WriteLine(s);
}

// Backtracking search for sets of K primes.
static void Search(List<int>[] comp, HashSet<int>[] compHS, List<int> primes,
                   List<int> currentSet, List<int> candidates, int K, List<int> sums)
{
    if (currentSet.Count == K)
    {
        int sum = 0;
        foreach (var idx in currentSet)
            sum += primes[idx];
        sums.Add(sum);
        return;
    }

    for (int i = 0; i < candidates.Count; i++)
    {
        int candidateIndex = candidates[i];
        List<int> newCandidates = new List<int>();
        // Only consider candidates later in the list to maintain increasing order.
        for (int j = i + 1; j < candidates.Count; j++)
        {
            int nextCandidate = candidates[j];
            if (compHS[candidateIndex].Contains(nextCandidate))
                newCandidates.Add(nextCandidate);
        }
        currentSet.Add(candidateIndex);
        Search(comp, compHS, primes, currentSet, newCandidates, K, sums);
        currentSet.RemoveAt(currentSet.Count - 1);
    }
}

// Sieve of Eratosthenes to get all primes less than N.
static List<int> SievePrimes(int N)
{
    bool[] isComposite = new bool[N];
    List<int> primes = new List<int>();
    for (int i = 2; i < N; i++)
    {
        if (!isComposite[i])
        {
            primes.Add(i);
            for (int j = i * 2; j < N; j += i)
                isComposite[j] = true;
        }
    }
    return primes;
}

// Cached check for concatenated primes.
static bool IsConcatPrime(int x)
{
    if (primeCache.ContainsKey(x))
        return primeCache[x];
    bool result = IsPrimeMR(x);
    primeCache[x] = result;
    return result;
}

// Deterministic Miller-Rabin for 32-bit numbers using bases 2, 7, and 61.
static bool IsPrimeMR(int n)
{
    if (n < 2) return false;
    if (n % 2 == 0) return n == 2;

    // Write n-1 as d * 2^s.
    int d = n - 1;
    int s = 0;
    while ((d & 1) == 0)
    {
        d /= 2;
        s++;
    }

    int[] bases = { 2, 7, 61 };
    foreach (int a in bases)
    {
        if (a % n == 0) continue;
        long x = ModPow(a, d, n);
        if (x == 1 || x == n - 1)
            continue;
        bool composite = true;
        for (int r = 1; r < s; r++)
        {
            x = (x * x) % n;
            if (x == n - 1)
            {
                composite = false;
                break;
            }
        }
        if (composite)
            return false;
    }
    return true;
}

// Fast modular exponentiation.
static long ModPow(long a, long d, long mod)
{
    long result = 1;
    a %= mod;
    while (d > 0)
    {
        if ((d & 1) == 1)
            result = (result * a) % mod;
        a = (a * a) % mod;
        d >>= 1;
    }
    return result;
}

}

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

public class Solution {

private static List<Long> sums = new ArrayList<>();

// Merge two numbers, "append their digits"
private static long merge(long a, long b) {
    long shift = 1;
    while (shift <= b) {
        shift *= 10;
    }
    return a * shift + b;
}

// Check if a number is prime
private static boolean isPrime(long p) {
    if (p < 2) return false;
    if (p == 2 || p == 3) return true;
    if (p % 2 == 0 || p % 3 == 0) return false;

    for (long i = 5; i * i <= p; i += 6) {
        if (p % i == 0 || p % (i + 2) == 0) return false;
    }
    return true;
}

// Check if two numbers can be merged and the result is still prime
private static boolean match(long a, long b) {
    return isPrime(merge(a, b)) && isPrime(merge(b, a));
}

// Find sets of primes of the specified size
private static void findSets(int size, List<Integer> primes) {
    for (int i = 0; i < primes.size(); i++) {
        int smallPrime = primes.get(i);
        if (smallPrime == 5) continue;

        List<Integer> candidates = new ArrayList<>();
        for (int j = i + 1; j < primes.size(); j++) {
            int largePrime = primes.get(j);
            if (match(smallPrime, largePrime)) {
                candidates.add(largePrime);
            }
        }

        if (size == 3) {
            checkTriple(smallPrime, candidates);
        } else if (size == 4) {
            checkQuadruple(smallPrime, candidates);
        } else if (size == 5) {
            checkQuintuple(smallPrime, candidates);
        }
    }
}

// Find and add sums for triplets
private static void checkTriple(int first, List<Integer> candidates) {
    for (int i = 0; i < candidates.size(); i++) {
        for (int j = i + 1; j < candidates.size(); j++) {
            if (match(candidates.get(i), candidates.get(j))) {
                sums.add((long) first + candidates.get(i) + candidates.get(j));
            }
        }
    }
}

// Find and add sums for quadruplets
private static void checkQuadruple(int first, List<Integer> candidates) {
    for (int i = 0; i < candidates.size(); i++) {
        for (int j = i + 1; j < candidates.size(); j++) {
            if (!match(candidates.get(i), candidates.get(j))) continue;

            for (int k = j + 1; k < candidates.size(); k++) {
                if (match(candidates.get(i), candidates.get(k)) && match(candidates.get(j), candidates.get(k))) {
                    sums.add((long) first + candidates.get(i) + candidates.get(j) + candidates.get(k));
                }
            }
        }
    }
}

// Find and add sums for quintuplets
private static void checkQuintuple(int first, List<Integer> candidates) {
    for (int i = 0; i < candidates.size(); i++) {
        for (int j = i + 1; j < candidates.size(); j++) {
            if (!match(candidates.get(i), candidates.get(j))) continue;

            for (int k = j + 1; k < candidates.size(); k++) {
                if (!match(candidates.get(i), candidates.get(k)) || !match(candidates.get(j), candidates.get(k))) {
                    continue;
                }

                for (int l = k + 1; l < candidates.size(); l++) {
                    if (match(candidates.get(i), candidates.get(l)) && match(candidates.get(j), candidates.get(l))
                            && match(candidates.get(k), candidates.get(l))) {
                        sums.add((long) first + candidates.get(i) + candidates.get(j) + candidates.get(k)
                                + candidates.get(l));
                    }
                }
            }
        }
    }
}

public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    int maxPrime = scanner.nextInt();
    int size = scanner.nextInt();
    scanner.close();

    List<Integer> primes = new ArrayList<>();
    primes.add(2); // Add 2 explicitly

    // Generate prime numbers using the Sieve of Eratosthenes
    boolean[] isPrime = new boolean[maxPrime + 1];
    Arrays.fill(isPrime, true);
    isPrime[0] = isPrime[1] = false;

    for (int i = 2; i * i <= maxPrime; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j <= maxPrime; j += i) {
                isPrime[j] = false;
            }
        }
    }

    for (int i = 3; i < maxPrime; i += 2) {
        if (isPrime[i]) {
            primes.add(i);
        }
    }

    findSets(size, primes);

    // Sort and print the sums
    Collections.sort(sums);
    for (long sum : sums) {
        System.out.println(sum);
    }
}

}

JAva code

4, 9, 14 cash are not work

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

public class Solution {

    private static List<Long> sums = new ArrayList<>();

    // Merge two numbers, "append their digits"
    private static long merge(long a, long b) {
        long shift = 10;
        while (shift <= b)
            shift *= 10;
        return a * shift + b;
    }

    // Check if a number is prime
    private static boolean isPrime(long p) {
        if (p < 2)
            return false;
        if (p < 4)
            return true;
        if (p % 2 == 0 || p % 3 == 0)
            return false;

        for (long i = 5; i * i <= p; i += 6) {
            if (p % i == 0 || p % (i + 2) == 0)
                return false;
        }

        return true;
    }

    // Check if two numbers can be merged in any way and the result is still prime
    private static boolean match(long a, long b) {
        return isPrime(merge(a, b)) && isPrime(merge(b, a));
    }

    // Find all sets of primes with the specified size
    private static void findSets(int size, List<Integer> primes) {
        int maxPrime = Collections.max(primes);

        for (int i = 0; i < primes.size(); i++) {
            int smallPrime = primes.get(i);
            if (smallPrime == 5)
                continue;

            List<Integer> candidates = new ArrayList<>();
            for (int j = i + 1; j < primes.size(); j++) {
                int largePrime = primes.get(j);
                if (match(smallPrime, largePrime)) {
                    candidates.add(largePrime);
                }
            }

            if (size == 3) {
                checkTriple(smallPrime, candidates);
            } else if (size == 4) {
                checkQuadruple(smallPrime, candidates);
            } else if (size == 5) {
                checkQuintuple(smallPrime, candidates);
            }
        }
    }

    // Find and add sums for triplets
    private static void checkTriple(int first, List<Integer> candidates) {
        for (int i = 0; i < candidates.size(); i++) {
            for (int j = i + 1; j < candidates.size(); j++) {
                if (match(candidates.get(i), candidates.get(j))) {
                    sums.add((long) first + candidates.get(i) + candidates.get(j));
                }
            }
        }
    }

    // Find and add sums for quadruplets
    private static void checkQuadruple(int first, List<Integer> candidates) {
        for (int i = 0; i < candidates.size(); i++) {
            for (int j = i + 1; j < candidates.size(); j++) {
                if (!match(candidates.get(i), candidates.get(j))) {
                    continue;
                }

                for (int k = j + 1; k < candidates.size(); k++) {
                    if (match(candidates.get(i), candidates.get(k)) && match(candidates.get(j), candidates.get(k))) {
                        sums.add((long) first + candidates.get(i) + candidates.get(j) + candidates.get(k));
                    }
                }
            }
        }
    }

    // Find and add sums for quintuplets
    private static void checkQuintuple(int first, List<Integer> candidates) {
        for (int i = 0; i < candidates.size(); i++) {
            for (int j = i + 1; j < candidates.size(); j++) {
                if (!match(candidates.get(i), candidates.get(j))) {
                    continue;
                }

                for (int k = j + 1; k < candidates.size(); k++) {
                    if (!match(candidates.get(i), candidates.get(k)) || !match(candidates.get(j), candidates.get(k))) {
                        continue;
                    }

                    for (int l = k + 1; l < candidates.size(); l++) {
                        if (match(candidates.get(i), candidates.get(l)) && match(candidates.get(j), candidates.get(l))
                                && match(candidates.get(k), candidates.get(l))) {
                            sums.add((long) first + candidates.get(i) + candidates.get(j) + candidates.get(k)
                                    + candidates.get(l));
                        }
                    }
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int maxPrime = scanner.nextInt();
        int size = scanner.nextInt();
        scanner.close();

        List<Integer> primes = new ArrayList<>();
        primes.add(2); // Add 2 since it's not generated

        // Find all primes up to the specified maxPrime
        for (int i = 3; i < maxPrime; i += 2) {
            boolean isPrime = true;
            for (int p : primes) {
                if (p * p > i) {
                    break;
                }
                if (i % p == 0) {
                    isPrime = false;
                    break;
                }
            }
            if (isPrime) {
                primes.add(i);
            }
        }

        findSets(size, primes);

        // Sort and print the sums
        Collections.sort(sums);
        for (long sum : sums) {
            System.out.println(sum);
        }
    }
}

This one is very complex; in Python had to end up doing lots of optimizations. Miller-Rabin can be made deterministic beneath a certain range, it is recommended to avoid the overhead of constant random. And clique hunting is easy with set operators if you have access to them. But you have to really squeeze every ounce of efficiency from every function; there are plenty of places to prune in the clique algorithms.

I didn't end up needing multiprocessing that xperroni mentions, I didn't like the idea of processing power being the key to algorithmic optimizations for Project Euler.

After working on it for days, I was finally able to pass all tests using a solution written in Python 3. My tips, in spoiler order:

Skip 2 and 5 in your prime sequence, since they will never be in any valid pairs.

Use a fast prime sieve (for example this one) to generate all primes in the range first, then look for connections.

As Ki Chun TONG suggested, use the generated prime list (or rather a set, for faster search times) as the first level in your prime checker, and Miller-Rabin as the second level if the number is not found there.

Divide the generated primes into two sets primes_1 = {3} | {p for p in primes if p % 3 == 1} and primes_2 = {3} | {p for p in primes if p % 3 == 2}, then process them separately — the reason this can be done is that if p1 % 3 == 1 and p2 % 3 == 2 or vice versa, then the concatenation of p1 and p2 will be divisible by 3, and therefore (p1, p2) is not a valid pair.

Use multiprocessing to process both of the above lists simultaneously.