[Question]
  [
This is a "counterpart" of another puzzle, [Eight coins for the fair king](https://puzzling.stackexchange.com/q/77750/44061) on Puzzling.SE.
You can read the above puzzle for the background. The details about this puzzle are as follows.
A set of 8 kinds of coins of different values are created, the king wants you to find out the maximum N such that any number of price from 0 to N can be paid with a combination no more than 8 coins and without charges.
For example, (taken from Glorfindel's answer). If a set of coins of values 1, 2, 5, 13, 34, 89, 233, 610 are given, your program should output 1596, because every number between 0 and 1596 (inclusive) can be represented by the sum of no more than 8 numbers from the given list (numbers may repeat), while 1597 cannot be represented in that way.
In a mathematical way, if the input is a set S consisting of 8 positive integers, the desired output N satisfies that for any number *n* between 0 and N, there exists x1, x2, x3, ..., x8 such that
$$x\_1 + x\_2 + ... + x\_8 = n \quad\textrm{and}\quad x\_1, x\_2, ...,x\_8 \in \{0\} \cup S$$
Your goal is to write a program, a function, or a snippet that takes 8 numbers as input, and output the maximum N as described above.
Rules:
* Flexible I/O allowed, so your program can take the input in any form that's best suitable. You may assume that the input numbers are sorted in the way that best suits your program.
	+ Please state it in your answer if your program depends on input order
* Input is a set of 8 different, positive integers (no zeros). The output is one non-negative integer.
	+ In case there's no 1 in the input set, your program should output 0 because any number from 0 to 0 satisfies the requirement.
	+ In the case of invalid input (the set contains zero, negative or duplicate numbers), your program can do anything.
* Standard loopholes are forbidden.
* Your program should run within a few minutes on a modern computer.
Test cases (mostly taken from the answers under the linked question on Puzzling):
```
[1, 2, 3, 4, 5, 6, 7, 8] => 64
[2, 3, 4, 5, 6, 7, 8, 9] => 0
[1, 3, 4, 5, 6, 7, 8, 9] => 72
[1, 2, 5, 13, 34, 89, 233, 610] => 1596
[1, 5, 16, 51, 130, 332, 471, 1082] => 2721
[1, 6, 20, 75, 175, 474, 756, 785] => 3356
```
This is a [code-golf](/questions/tagged/code-golf "show questions tagged 'code-golf'"), so the shortest program or snippet in each language wins!
  
[Answer]
# [Python 3](https://docs.python.org/3/), ~~113~~ 62 bytes
```
for i in[1]*3:x|={a+b for a in x for b in x}
while{i+1}&x:i+=1
```
Here `x` is the input as a set of ints, and `i` is the output.
[Try it online!](https://tio.run/##K6gsycjPM/5foWCrUG2oo2Cmo2BkoKNgbqqjYAgiTMxNQDygsLmFae3/tPwihUyFzLxow1gtY6uKGtvqRO0kBZBoIlBUoQLMTAIza7nKMzJzUqsztQ1r1SqsMrVtDf8XFGXmlWhkav4HAA "Python 3 – Try It Online")
(Thanks: Erik the Outgolfer, Mr. Xcoder, Lynn)
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 12 [bytes](https://github.com/DennisMitchell/jellylanguage/wiki/Code-page)
```
œċⱮ8Ẏ§ṢQJƑƤS
```
[Try it online!](https://tio.run/##y0rNyan8///o5CPdjzaus3i4q@/Q8oc7FwV6HZt4bEnw/8Ptj5rWuP//Hx1tqKNgpKNgrKNgoqNgqqNgpqNgrqNgEavDFY1FWEfBEiRjiE/GCCxsCFRgDFRhYQkUMQZyzAwNoApAskBdpoYgVQZAZcZALSbmIK6BhRFUEVCBEVDOHKQYRJiYm4B4INssTGNjAQ "Jelly – Try It Online")
Takes on average ~3.7 seconds to run all test cases on TIO on my phone, so surprisingly it is quite fast.
### Explanation
```
œċⱮ8Ẏ§ṢQJƑƤS     Monadic link / Full program.
  Ɱ8             Promote 8 to [1 ... 8] and for each value k:
œċ                    Generate all combinations of k elements from the list.
    Ẏ§           Tighten, then sum. Flatten to a 2D list then sum each.
      ṢQ         Sort the result and remove equal entries.
        JƑƤ      For each prefix of this list, return 1 if it is equal to its length range, 0 otherwise.
           S     Finally, sum the result (counts the 1's which is equivalent to what is being asked).
```
[Answer]
## Haskell, ~~56~~ 50 bytes
```
g c=[x|x<-[1..],all((/=x).sum)$mapM(0:)$c<$c]!!0-1
```
[Try it online!](https://tio.run/##y0gszk7Nyfn/P10h2Ta6oqbCRjfaUE8vVicxJ0dDQ9@2QlOvuDRXUyU3scBXw8BKUyXZRiU5VlHRQNfwf25iZp6CrUJBUWZeiYKKQrpCtKGOkY6FjrGRjqGhIZgwARGmIMIs9j8A "Haskell – Try It Online")
A brute force approach. Add `0` to the list of coins and try all combinations of 8 picks. Find the first number `n` that is not equal to the sum of any of the picks and return `n-1`.
Takes about 5m30s for `[1, 2, 5, 13, 34, 89, 233, 610]` on my 7 year old laptop hardware.
Edit: -6 bytes thanks to @Ørjan Johansen
An even shorter version (-2 bytes, again thanks to @Ørjan Johansen) is
### Haskell, 48 bytes
```
g c=[x|x<-[1..],all((/=x).sum)$mapM(:0:c)c]!!0-1
```
but it uses significantly more memory and runs into heavy paging on my machine and does not finish "within a few minutes".
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 9 bytes
```
Żœċ8§ḟ’$Ṃ
```
[Try it online!](https://tio.run/##y0rNyan8///o7qOTj3RbHFr@cMf8Rw0zVR7ubPp/uP1R0xoF9///o6MNdRSMdBQUjIHYBIgVTEGEGYgwBxEKFrFcOtFAFTAFaPIWYEWWIEWGRCoygigwBCk2Bqm2sAQKGoO4ZoYGUEUgBUADTA1BCg2AJhsDtZmYg7gGFkZQRUAFRkA5c5BiEGFibgLigSw2tzCN5YoFAA "Jelly – Try It Online")
### How it works
```
Żœċ8§ḟ’$Ṃ  Main link. Argument: A (array)
Ż          Prepend a 0 to A.
 œċ8       Take all combinations of length 8, with repetitions.
    §      Take the sum of each combination.
       $   Combine the two links to the left into a monadic chain.
      ’      Decrement all sums.
     ḟ       Filterfalse; keep only sums that do not appear in the decremented sums.
        Ṃ  Take the minimum.
```
[Answer]
# [Wolfram Language (Mathematica)](https://www.wolfram.com/wolframscript/), 53 bytes
```
LengthWhile[CoefficientList[(1+Tr[x^#])^8,x],#>0&]-1&
```
[Try it online!](https://tio.run/##fY1NC4JAFEX/ygNBip7k@DXjIgnaumgRtBhGEBlzIA1sFoL42@1NuIw2D@495/L62na6r61p6rWFE6ylHh62u3fmqeXlpdvWNEYPtjRvK3fscBvlVHlqXwmcFHpF6KuA@et1NIOVHgQFtNJTCnw4nmGeGUKEECMkCClChsARxIIw/6gRckfYPxJ9a0ZCTIbIqYkpZCzcBEdplTJnhaTFNEm4i6GINomEiBh3sjsJT1xy30S6LOsH "Wolfram Language (Mathematica) – Try It Online")
[Answer]
# JavaScript (ES6), ~~100 88 80~~ 76 bytes
This is essentially a brute-force search, but enhanced with pruning to speed it up. The average execution time for the test cases is close to 1 second on TIO.
Assumes that the input array is sorted from highest to lowest.
```
a=>[...Array(a[0]*9)].findIndex(g=(i=8,s)=>s*i>0?a.every(x=>g(i-1,s-x)):s)-1
```
[Try it online!](https://tio.run/##jc/NjoMgFAXg/TwFS2iQgsiPk@BklvMMxgWpaGganUjT2Ke3V7tpnC6G3U3Od8/l7G8@nab4e82GsQ1L5xbvqpox9j1N/o59zZtDSRrWxaH9Gdow497h6CxNxFXpECv@5Vm4hemOZ1f1OGaCpmwm5DORTCyncUjjJbDL2OMO15YiQ5GmSFFUUCQpyikSDSHo5R2PSBcfO1lS9Ab/lfxf8E2lyfdSCw4VEuIWlkiQQm47Xm8GKVSp91ZwC6nCCIByzUvYpWASzzM2DzY3udhbYyFglF79Wmq2EWr59olnNVgplV4e "JavaScript (Node.js) – Try It Online")
### Commented
```
a =>                      // a[] = input array
  [...Array(a[0] * 9)]    // create an array of 9 * max(a) entries
  .findIndex(             // find the position of the first truthy result
    g = (i = 8, s) =>     // g = recursive function taking a counter i, initialized to 8
                          //     and a sum s, initialized to the position in the above array
      s * i > 0 ?         //   if s is positive and i is not equal to 0:
        a.every(x =>      //     for each value x in a[]:
          g(i - 1, s - x) //       do a recursive call with i - 1 and s - x
        )                 //     end of every()
      :                   //   else:
        s                 //     yield s (s = 0 means success and makes findIndex go on)
  ) - 1                   // end of findIndex(); decrement the result
```
[Answer]
# [Python 2](https://docs.python.org/2/), 145 bytes
```
from itertools import*
x=set(map(sum,reduce(chain,map(combinations_with_replacement,[input()]*9,range(9)))))
print~-min(set(range(1,max(x)+2))-x)
```
[Try it online!](https://tio.run/##JYxBCoMwFET3niLLxEaoorUuehIRSW1aP5ifkHxpuunVU0NnMTBv4LkPrRablJ7eGgakPVm7BQbGWU9lEW9BEzfK8bAb6fVjXzRfVgUoM1ysuQMqAothfgOts9duU4s2GkmOgG4nLqZykF7hS/NB5BTOA9K3MoA86/9ffRgjj@LUCFFFkdJYS3aRrDlL1neS1bnavs3rwP21m34 "Python 2 – Try It Online")
[Answer]
# [Pari/GP](http://pari.math.u-bordeaux.fr/), 57 bytes
```
a->n=-1;while(polcoeff((1+sum(i=1,8,x^a[i]))^8,n++),);n-1
```
[Try it online!](https://tio.run/##fY3dCoMwDEZfJXjVYgrGn1kRfRFRKGNuBafFbWx7epcML8duQr7vnJDgVm/OYRuhgc2Zdm4M1c@Ln04qLNNxOY2jUhTfHlflG0KLr8F1vtd6sDjHsUZdz4Y2F8L0Vg5MC2H1853XSEIEo3JaI3QdIaQIGUKOUCAcEEoE2zP6USNUQugfSb81sZCxYStuMg4HSnZBKF8VJFbCWsYneSkxsekusZAyK0WWkZe5JPlmi77X2wc "Pari/GP – Try It Online")
[Answer]
# [Python 2](https://docs.python.org/2/), ~~125~~ ~~115~~ 111 bytes
```
lambda c:sum(i==j for i,j in enumerate(sorted(set(map(sum,product([0]+c,repeat=8))))))-1
from itertools import*
```
[Try it online!](https://tio.run/##fZDBboMwDIbPy1P4mG6uRIAWWoknYRwYBC1VQ6LEHPb0zEY9TvPB0v//nxPZ8Ye@w1ruS/e5P0f/NY8w3fPmteu6BywhgcMHuBXsunmbRrI6h0R21tmS9mPUDGNMYd4m0n0xfEyYbLQjde3pqLNRSwoeHNlEITwzOB/5ifedbKYMHfSqNwglQoVQI1wQrggNQjug6v@wEW6SmP@S8rANAxUT7Y2disXVFC9AUp66GKEKxioeqRuRRVu@IAZKzhqBpdVNLUp@ay/MDErJiWQRudGx0F29xeRWgkWLPu2/ "Python 2 – Try It Online")
Expects a list of integers as input.
Explanation:
```
# an anonymous function
lambda c:
                                                          # get all length-8 combinations of values, from (0,0,0,0,0,0,0,0) to (8,8,8,8,8,8,8,8)
                                                          # zero is added to ensure that combinations of fewer than 8 coins are represented Ex:(1,0,0,0,0,0,0,0)
                                                          product([0]+c,repeat=8)
                                                  # for each combination, sum the values
                                                  map(sum,.......................)
                                       # get unique values, then sort them smallest to largest
                                       sorted(set(................................))
             # for each index, value pair, return if the index is equal to the value
             i==j for i,j in enumerate(.............................................)
         # in Python arithmetic, False is 0 and True is 1. So, count how many items match their index.
         # Since zero was added to the list, there will always be one extra match (0==0). So offset by one.
         sum(........................................................................)-1
from itertools import*
```
[Answer]
# Perl6, 65 63 41 bytes (39 37 chars)
```
{@_=(0,|@_)X+(0,|@_)for ^3;($_ if $_==$++for @_.sort.unique)-1}
```
[Try it online!](https://tio.run/##K0gtyjH7n1upoJZq@7/aId5Ww0CnxiFeM0IbwtArzcssLE3VTMsvUogzttZQiVfITFNQibe1VdHWBgkClRTnF5XA1Oka1v4vTgQZp2GoY6ZjZKBjbqpjCMQm5iZAppmOuYWppjXXfwA "Perl 6 – Try It Online")
This is an anonymous block that gets passed its data as an array. The `(0,|@_)` is a quick way to add a `0` to `@_`, and even though it's done twice, it's still a bit shorter than `@_.push: 0;` which would then need spaces after the `_`. This is a brute force approach that cheeses a bit on the fact that it's 8 combinations. After cross adding, an anonymous list is created for sequential values. With math operators, lists evaluate to their length, so the -1 pulls double duty: accounting for the 0 and coercing to Int. 
This can take its sweet time, but by changing one or both `(0,|@_)` to `(0,|@_.unique)` before the first `for` it can be sped up considerably. That adds **+7** (runtime <60s) or **+14** (runtime <10s) to the score if you feel the first is too slow (I did this for the linked code to avoid timeouts after 60 seconds).
**Edit:** JoKing in the comments improved it (same idea, cross add, then return the last consecutive result) to an astonishing 39 chars (41 bytes):
```
{(@_=@_ X+0,|@_)xx 3;first *+1∉@_,^∞}
```
[Try it online!](https://tio.run/##dc7PasJAEAbw@z7FIFKTOsj@y26CpKSH3nouhZCGHCIEUpXEg6Le7Uv04XyRdGbpsb0sfPP9Zth9O/Ru@jzBQ5tP56io86KG96XES1HHxyOY9aYbxgM8LtX99lXU@HG/fV@nzW6AqO@27RjDWQAAXZg3@Wrc990hmkH@BLN4zcXYnKCNLvOmlNXq5e35NcYF1wukkarEVUylQtAIBsEiJAgOwSOkFTNnRflHh5CFWgpe/q/1Wvzepk6RMsTSjCaGglMyKJVkLjhGdCFRjCVpQ5vWc5SpDlZ7rYIlp4l43uHHesuJP5AmgRqTuB8 "Perl 6 – Try It Online")
The final tabulation doesn't need a 0, saving a few bytes by only needing to add 0 in once. The `xx 3` mimics the for loop (still cheeses on the coins being a power of 2). The `first` sub returns the first number in the infinite list `0..*` (`^Inf` is possible too, but doesn't save space) whose `+1` is not a member of the cross added list. Like mine, it's slow, so add **+7** for a `unique` after the first equals if you feel it's too slow for guidelines.
[Answer]
# [JavaScript (Node.js)](https://nodejs.org), ~~171~~ ~~145~~ 115 bytes
```
f=(s,n=3)=>n?f(s=new Set(a=[0,...s]),n-1,a.map(m=>a.map(n=>s.add(m+n)))):Math.min(...[...s].filter(m=>!s.has(m+1)))
```
[Try it online!](https://tio.run/##lc6xboMwEIDhvU9x3Wz1csIYAklk@gSdOqIMVjANFZgoRu3j07t0q5KhHiyf9X@WP/2XT6frcFk2ce7CuvZOJYzOatfE114lF8M3vIdFeddmSETpqDFuDHqa/EVNrvk9RNck8l2nppeoee3f/HKmaYiKTXtz1A/jEq5inhOdfeLWcLo@neaY5jHQOH@oXrUGIUewCAVCibBFqBDqo9aHv@WdDGF3rzT/KfNbZhhYFvWObywPW5M9AFLzq6URlTGz/ERRyZjV@QPEIOe2EixbURUyye/qUsz6Aw "JavaScript (Node.js) – Try It Online") Port of @Mark's Python 3 answer. 108 bytes in Firefox 30-57:
```
f=(s,n=3)=>n?f(new Set((for(n of s=[0,...s])for(m of s)n+m)),n-1):Math.min(...[...s].filter(m=>!s.has(m+1)))
```
[Answer]
# [Wolfram Language (Mathematica)](https://www.wolfram.com/wolframscript/), 46 bytes
```
0//.x_/;Min[Tr/@FrobeniusSolve[#,x+1]]<9:>x+1&
```
[Try it online!](https://tio.run/##fdBNS8NAEAbge37FgFBqHLrf2aQ1JSdvgqC3UiSWFAM2hWSVQshvjzM1uUkvy77L8w7DnsrwWZ3KUB/K8ZiPUojV5V1snutm99aK4qk9f1RN/d29nr9@qt0dXh7Ufv@Yrbd0WYyh6kKX91GvEDSCQbAIDiFB8AjpgLCM8y0kNr6P@n8AQjYbyUTdJF5PRl@BImrIphm9GAqJkjNVLksmzJJmOcUNSRVDdes5ylTPBe21mgqENTnPRT6st5x4n9QNf9wYx/OH6KWtm1DER1Fc/2L8BQ "Wolfram Language (Mathematica) – Try It Online")
Brute force approach: checks integers counting upward until it reaches a value that can't be paid for in 8 coins. Very, very slow (tio times out), but I'm fairly sure the condition is correct.
[Answer]
# [Clean](https://github.com/Ourous/curated-clean-linux), 161 bytes
```
import StdEnv,Data.List
$l=:[1:_]#k=sort(nub(map sum(iter 8(concatMap(\[h:t]=[[e,h:t]\\e<-[0:l]|e>=h]))[[0]])))
=length(takeWhile((>=)1)(zipWith(-)(tl k)k))
$_=0
```
[Try it online!](https://tio.run/##JY6xasMwFEX3fIWgHiSQixw3bTBRpmQopFDIkEEW4dVRYmFJNvZzoaXfXlWh07mXe4bbOAMh@v4yO0M82BCtH/oRyREv@/DJd4DweLATLjInK1VUZ/3QySkZNMwf1MNAptlTi2Yka9r0oQF8g4HWqq1QS6UMv4e6NptcicrpH7OVrWZMKaET2EI6E27YUoTOnFrrDKVbyQpGv@1wsmnIGUVHOtYlOTtLEY8I6aAkGVEFJytOiueEFItScFKWS06eXu5VrJc6/jZXB7cp5q@HuPsK4G3zX94d4LUffczbuBJC@D8 "Clean – Try It Online")
]