Cipher Catalog Cover Problem

Cipher Catalog Cover Problem — ExecCode Hard DSA Practice

Solve the Cipher Catalog Cover problem on ExecCode. Free online hard DSA practice in String. Write and run code in Java, C++, Python — no signup required to run.

Problem description

Problem Statement You get a text T and K catalog patterns. Each pattern has a cost. Do two jobs: Cover T by placing catalog patterns end to end. No leftover characters. Minimize the total cost. If it is impossible, print -1 for the cover. Count how many times each pattern appears in T as a substring. Overlaps count. Print the cover cost first. Then print the K counts. Input Format The pattern/cost pair repeats K times. Output Format First line is the cover cost, or -1. Then one count per catalog pattern, in input order. Constraints Letters are lowercase. Example 1 Input The text is aab. Two patterns: aa costs 3, b costs 1. Cover: aa then b. Cost 4. aa appears once. b appears once. Output Example 2 Input Cover: a then b. Cost 2. Each letter appears once. Output Example 3 Input One pattern is the whole text. Cover cost 4. It appears once. Output

Examples

Input aab 2 aa 3 b 1; Output 4 1 Input ab 2 a 1 b 1; Output 2 1 Input abc 1 abc 4; Output 4 1

Constraints

1 ≤ |T| ≤ 400, 1 ≤ K ≤ 40, 1 ≤ |pattern| ≤ 40, 0 ≤ cost ≤ 1e9.

Practice Cipher Catalog Cover free on ExecCode. Browse DSA problems, topic map, and placement guides.