Construct Best String

Problem Statement

Construct Best String You are given N words LIST[0] … LIST[N-1] , a score POINTS[i] for each word, and an integer limit . Build a string ANS whose length is at most limit . Its total score is computed by scanning ANS and paying POINTS[i] for every occurrence of LIST[i] inside it: a word may occur many times and each occurrence is paid for again; occurrences of different words may overlap , and each one is still paid for; two occurrences of the same word may overlap each other, and both are paid for. For example, with LIST = {pack, acknowledge, edged} the string "packnowledged" contains "pack" , "acknowledge" and "edged" all at once, so all three scores are collected. Print the largest total score any such ANS can reach. The empty string is allowed and scores 0 , so the answer is never negative. Input Format Line 1: the integer N . Lines 2 … N+1: the words LIST[0] … LIST[N-1] , one per line. Lines N+2 … 2N+1: the integers POINTS[0] … POINTS[N-1] , one per line. Line 2N+2: the integer li