Maximal Substring Construction In this challenge, you are passed two things:


A string length, N
A list of strings, L, each with an assigned point value.  Any string that is not passed in has a point value of 0


You need to construct a string of length N such that the sum of all substring points is as large as possible.

For example:

5 [("ABC", 3), ("DEF", 4), ("CDG", 2)]


should output

ABCDG


Because the two substrings with points (ABC and CDG) have a total of 5 points, and no other possible construction can give 5 or more points.

Substrings can be used multiple times in a string, and can overlap.  You can assume that the points will always be positive, the substring lengths will be between 1 to N characters longs, and that N &gt; 0.  If multiple constructions are maximal, print any one of them.

Your program must run in a reasonable amount of time (no more than a minute for each of the examples):

1 [("A", 7), ("B", 4), ("C", 100)]     =&gt; C
2 [("A", 2), ("B", 3), ("AB", 2)]      =&gt; AB
2 [("A", 1), ("B", 2), ("CD", 3)]      =&gt; BB
2 [("AD", 1), ("B", 2), ("ZB", 3)]     =&gt; ZB
3 [("AB", 2), ("BC", 1), ("CA", 3)]    =&gt; CAB
3 [("ABC", 4), ("DEF", 4), ("E", 1)]   =&gt; DEF
4 [("A", 1), ("BAB", 2), ("ABCD", 3)]  =&gt; AAAA or ABAB or BABA or ABCD
5 [("A", 1), ("BAB", 2), ("ABCD", 3)]  =&gt; BABCD or BABAB
5 [("ABC", 3), ("DEF", 4), ("CDG", 2)] =&gt; ABCDG
5 [("AB", 10), ("BC", 2), ("CA", 2)]   =&gt; ABCAB
6 [("AB", 10), ("BC", 2), ("CA", 2)]   =&gt; ABABAB
8 [("AA", 3), ("BA", 5)]               =&gt; BAAAAAAA
10 [("ABCDE", 19), ("ACEBD",  18), ("ABEDC", 17), ("BCEDA", 16), ("EBDAC", 15), ("BACD", 14), ("CADB", 13), ("ABDC", 12), ("CABD", 11), ("EBDC", 10), ("ACE", 9), ("CBA", 8), ("AEC", 7), ("BE", 6), ("AE", 5), ("DC", 4), ("BA", 3), ("A", 2), ("D", 1)]
=&gt; ACEBDACEBD


This is a code-golf, so prepare your shortest answer in your favorite language!
Python 2.7, 503 Bytes
This isn't particularly golfed, nor is it particularly efficient; it's just a relatively condensed enumeration of feasible strings that are brute-forced.  I don't think it would be too hard to create an admissible heuristic to use with A*, which would probably be a bit quicker.  I didn't bother doing that, though, because this method solves all of the examples in about 47 seconds on my laptop.
import re
v=lambda l,s:sum([len([m.start() for m in re.finditer('(?=%s)'%u,s)])*v for u,v in l])
def m(n,l,e):
 if len(e)==n:
  yield e
 else:
  u=1
  for s,v in sorted(l,key=lambda j:j[1],reverse=True):
   for i in range(len(s)-1,0,-1):
    if len(e)+len(s)-i &lt;= n and e.endswith(s[:i]):
     for r in m(n,l,e+s[i:]):
      u=0;yield r
   if len(e)+len(s)&lt;=n:
    for r in m(n,l,e+s):
     u=0;yield r
  if u:
   yield e
def p(n,l):
 b,r=-1,0
 for s in m(n,l,''):
  a=v(l,s)
  if a&gt;b:b,r=a,s
 return r

To test it:
if __name__ == &quot;__main__&quot;:
    for n, l in [
            (1, [(&quot;A&quot;, 7), (&quot;B&quot;, 4), (&quot;C&quot;, 100)]),     # =&gt; C
            (2, [(&quot;A&quot;, 2), (&quot;B&quot;, 3), (&quot;AB&quot;, 2)]),      # =&gt; AB
            (2, [(&quot;A&quot;, 1), (&quot;B&quot;, 2), (&quot;CD&quot;, 3)]),      # =&gt; BB
            (2, [(&quot;AD&quot;, 1), (&quot;B&quot;, 2), (&quot;ZB&quot;, 3)]),     # =&gt; ZB
            (3, [(&quot;AB&quot;, 2), (&quot;BC&quot;, 1), (&quot;CA&quot;, 3)]),    # =&gt; CAB
            (3, [(&quot;ABC&quot;, 4), (&quot;DEF&quot;, 4), (&quot;E&quot;, 1)]),   # =&gt; DEF
            (4, [(&quot;A&quot;, 1), (&quot;BAB&quot;, 2), (&quot;ABCD&quot;, 3)]),  # =&gt; AAAA or ABAB or BABA or ABCD
            (5, [(&quot;A&quot;, 1), (&quot;BAB&quot;, 2), (&quot;ABCD&quot;, 3)]),  # =&gt; BABCD or BABAB
            (5, [(&quot;ABC&quot;, 3), (&quot;DEF&quot;, 4), (&quot;CDG&quot;, 2)]), # =&gt; ABCDG
            (5, [(&quot;AB&quot;, 10), (&quot;BC&quot;, 2), (&quot;CA&quot;, 2)]),   # =&gt; ABCAB
            (6, [(&quot;AB&quot;, 10), (&quot;BC&quot;, 2), (&quot;CA&quot;, 2)]),   # =&gt; ABABAB
            (8, [(&quot;AA&quot;, 3), (&quot;BA&quot;, 5)]),               # =&gt; BAAAAAAA
            (10, [(&quot;ABCDE&quot;, 19), (&quot;ACEBD&quot;,  18), (&quot;ABEDC&quot;, 17), (&quot;BCEDA&quot;, 16), (&quot;EBDAC&quot;, 15), (&quot;BACD&quot;, 14), (&quot;CADB&quot;, 13), (&quot;ABDC&quot;, 12), (&quot;CABD&quot;, 11), (&quot;EBDC&quot;, 10), (&quot;ACE&quot;, 9), (&quot;CBA&quot;, 8), (&quot;AEC&quot;, 7), (&quot;BE&quot;, 6), (&quot;AE&quot;, 5), (&quot;DC&quot;, 4), (&quot;BA&quot;, 3), (&quot;A&quot;, 2), (&quot;D&quot;, 1)]) # =&gt; ACEBDACEBD
    ]:
        print p(n, l)

Explanation
The v function simply calculates the value of a given string by searching for all occurrences of the substrings in L.  The m function enumerates all strings of length n with prefix e that can be generated from the substrings in l.  m recursively calls itself; the first call should pass in '' for e.  For example:
&gt;&gt;&gt; for s in m(4, [(&quot;A&quot;, 1), (&quot;BAB&quot;, 2), (&quot;ABCD&quot;, 3)], ''):print s
ABCD
BABA
ABCD
ABAB
AAAA

The p function simply loops through all possible strings (as enumerated by m) and returns the one with highest value (as determined by v).
Note that the m function actually prioritizes the enumeration by sorting based on substrings' values.  This turns out to be unnecessary to ensure optimality, and it actually hinders efficiency a bit; I could save ~20 or so bytes by removing it.