def form_str(n, subs, main):
    m_len = len(main)
    dp = [float('inf')] * (m_len + 1)
    dp[0] = 0

    for i in range(m_len + 1):
        if dp[i] == float('inf'):
            continue
        for s, c in subs:
            s_len = len(s)
            max_olap = min(i, s_len)
            for olap in range(max_olap + 1):
                start = i - olap
                end = start + s_len
                if end > m_len:
                    continue
                if start >= 0:
                    if main[start:i] == s[:olap]:
                        if main[i:end] == s[olap:]:
                            dp[end] = min(dp[end], dp[i] + c)

    return "Impossible" if dp[m_len] == float('inf') else dp[m_len]

n = int(input())
subs = []
for _ in range(n):
    ln = input().strip()
    if not ln:
        continue
    parts = ln.split()
    if len(parts) != 2:
        w = " ".join(parts[:-1])
        cost = int(parts[-1])
    else:
        w, cost = parts[0], int(parts[1])
    subs.append((w, cost))
main = input().strip()
subs = [(s, c) for s, c in subs if s in main]
print(form_str(n, subs, main), end="")

Check your application status -Barclays

void sort_students(struct Student arr[], int n) {
    struct Student temp;
    for (int i = 0; i < n-1; i++) {
        for (int j = i+1; j < n; j++) {
            if (arr[i].score < arr[j].score ||
                (arr[i].score == arr[j].score && strcmp(arr[i].first_name, arr[j].first_name) > 0) ||
                (arr[i].score == arr[j].score && strcmp(arr[i].first_name, arr[j].first_name) == 0 && strcmp(arr[i].last_name, arr[j].last_name) > 0)) {
                temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
    }
}