[Question]
  [
In this challenge, you are passed two things:
1. A string length, `N`
2. 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 > 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)]     => C
2 [("A", 2), ("B", 3), ("AB", 2)]      => AB
2 [("A", 1), ("B", 2), ("CD", 3)]      => BB
2 [("AD", 1), ("B", 2), ("ZB", 3)]     => ZB
3 [("AB", 2), ("BC", 1), ("CA", 3)]    => CAB
3 [("ABC", 4), ("DEF", 4), ("E", 1)]   => DEF
4 [("A", 1), ("BAB", 2), ("ABCD", 3)]  => AAAA or ABAB or BABA or ABCD
5 [("A", 1), ("BAB", 2), ("ABCD", 3)]  => BABCD or BABAB
5 [("ABC", 3), ("DEF", 4), ("CDG", 2)] => ABCDG
5 [("AB", 10), ("BC", 2), ("CA", 2)]   => ABCAB
6 [("AB", 10), ("BC", 2), ("CA", 2)]   => ABABAB
8 [("AA", 3), ("BA", 5)]               => 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)]
=> ACEBDACEBD
```
This is a [code-golf](/questions/tagged/code-golf "show questions tagged 'code-golf'"), so prepare your shortest answer in your favorite language!
  
[Answer]
# Python3, 383 bytes:
```
lambda t,s,k={}:max(f(s,'',t,0,k),key=lambda x:x[1])[0]
C=lambda l,a:(l[:len(a)]==a)+(0if''==l else C(l[1:],a))
def U(l,a,k):
 if(l,a)in k:return k[(l,a)]
 k[(l,a)]=C(l,a);return k[(l,a)]
def f(s,l,t,p,k):
 if(T:=len(l))==t:yield(l,sum(b*U(l,a,k)for a,b in s));return
 for a,b in s:
  for i in range(len(a)):
   if l[T-i:]==a[:i]and T<len(L:=(l[:T-i]+a))<=t:yield from f(s,L,t,p+b,k)
```
[Try it online!](https://tio.run/##nZPBjtsgEIbvfgqUS6ChkknWaUqXgw1OL3tML3V9IIrdWiFOZHulRFWfPQVscHazPWxPHuCbmf8f8OnS/TrWi9Wpua7Zj6uSh@1Ogg63eM9@/6EHeYYlbPF0ijsc4j3C@@LCBupMzxnJURbmAXd7CksKVUZVUUOJcsYkmsGwKqdTxhQoVFsArs8JzbFEKNgVJfgGdZIuTQNQlSZGVQ32tCm650YHmd3KAx8xbr9fXgOmltGqtNSTr7ehzGhRCDHW0UtVqJ3m2@cD3H5wnctjAyTeAt23Ra5wAG63dTG7rsyqkfXPAvYWTRugGwGVbT5W1DjOaJXLegc2jwZ5oswMRB/mM40/OhWgbI4HK/jJCJ5ttZDrqanqDq4hwSCDk3iCwSeEAZwkOnqwEdcRCUOU6@k5eu7puacXNooTu/k2TDzcp3Fh83JwT4s38O99m9vai54emYT7RB7/E@fenUjXPk5t6i0fYY8v7nAuvt55fXjt9UaariPuFEX/mfAOTdE4IxKOQ5qPQ3rJL9/Jr3o@9oISE0Yvr5WETrewY/7cO@RpYiwCshocp8Je4PAIeSrsaJb9/SQitqfR0MaOhwzOY2EVu2fY13GibRdCXBk@etMS9KKXw63yQUrKx5/BIMth23qzcx9fUTKaH38K4Z7T9S8)
[Answer]
# 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 <= n and e.endswith(s[:i]):
     for r in m(n,l,e+s[i:]):
      u=0;yield r
   if len(e)+len(s)<=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>b:b,r=a,s
 return r
```
To test it:
```
if __name__ == "__main__":
    for n, l in [
            (1, [("A", 7), ("B", 4), ("C", 100)]),     # => C
            (2, [("A", 2), ("B", 3), ("AB", 2)]),      # => AB
            (2, [("A", 1), ("B", 2), ("CD", 3)]),      # => BB
            (2, [("AD", 1), ("B", 2), ("ZB", 3)]),     # => ZB
            (3, [("AB", 2), ("BC", 1), ("CA", 3)]),    # => CAB
            (3, [("ABC", 4), ("DEF", 4), ("E", 1)]),   # => DEF
            (4, [("A", 1), ("BAB", 2), ("ABCD", 3)]),  # => AAAA or ABAB or BABA or ABCD
            (5, [("A", 1), ("BAB", 2), ("ABCD", 3)]),  # => BABCD or BABAB
            (5, [("ABC", 3), ("DEF", 4), ("CDG", 2)]), # => ABCDG
            (5, [("AB", 10), ("BC", 2), ("CA", 2)]),   # => ABCAB
            (6, [("AB", 10), ("BC", 2), ("CA", 2)]),   # => ABABAB
            (8, [("AA", 3), ("BA", 5)]),               # => 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)]) # => 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:
```
>>> for s in m(4, [("A", 1), ("BAB", 2), ("ABCD", 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.
[Try it online!](https://tio.run/##lZTRbpswFIbveYqjTFVgdaOQtF3HSicw2V5gV0URIoqzugM3siFTnz61jw0kaXpRXxBjn//jnP/Y2b42Ty9itt/zevsiG5DM28VVWa/WJVRERaqt/bxiws/riWpK2fgBbF4k1MCFDp5suFjzhkl/7P@ML1QwvmiJCpbB1x2GtWRnAqtl4K3ZBmpfkIqwIPKAb8BgWRDHQr/CK2fVGpgHrFLMLLRxqJ8GoixE6fzY2q/IP/bapfgcPefhkki2Y1Kx@I9sEW51HHMsxV/mm0@p4CokU3IV2oghg0u3y@E@BgGl0HlMmFir/7x58lUe8aWTIFYarKvkUuU86nd1ztMfthDpnfnCvS31HKZDHBM0oMWNzh1j4tZoTPyKyNiU5FmXBt54jLgy3mm3VGBB5cMqMoqSKE93rmmlNmevN4pClDUrCohjGBVFXXJRFKMhUUGgMuzcFWmHHxLI/VEyIvAtIOCPUj27xhnVs3A61aeAYOgXiB@AHqtnvXrWq@c4S1Jc7MRWnaQfycNebkE0Q9KxPD0vz87oH9MjPcofT@RzKx9EKe1JNDnU29KTD/S0tyxb/OrnC2RZAOr15rH@@rT6g1Q09cABa54eoBuZ6Djzq3/cO82OwTefA6dmrSOmZ1FY4/xdjTT73XfZNVgvnSfgaRpsng02zw5d0oTTHG4/S3hfxp1FJH0VqZneDOerH84RO06uyrQzI8PmfreG0kVqHIXwzhm8yPAcuftEFxl24taeijRLcPfGpYHdCJ2dSYZFdjfIcro68Sth2GHoYIdOQb/YdChW5lJZ0OFem5Bbt4y1YzOHs5sO5gz3OXOH2DlLMX39QGOWUe/PVnLR4F8aVMH@DQ)
]