This is a "counterpart" of another puzzle, Eight coins for the fair king 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 quadtextrm{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.


• 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 or negative 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, so the shortest program or snippet in each language wins!

Python 3, 91 bytes

def f(x):

 x=[0]+x

 for i in[1]*3:x={a+b for a in x for b in x}

 while{i}&x:i+=1

 return~-i

Try it online!

(Thanks @Erik the Outgolfer)

Jelly, 12 bytes

œċⱮ8Ẏ§ṢQJƑƤS

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).

Haskell, 56 50 bytes

g c=[x|x<-[1..],all((/=x).sum)$mapM(0:)$c<$c]!!0-1

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".

Python 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!

JavaScript (Node.js), 171 147 bytes

f=a=>a.map(n=>b.map((s,i)=>i++<8&&s.forEach(m=>b[i].add(m+n))),b=[...""+1e8].map(_=>new Set([0])))&&Math.min(...[...b=b[8]].filter(m=>!b.has(m+1)))

Try it online! I was worried that brute force would be too slow so I've gone for an efficient algorithm. The ith set in the array b contains the values obtained from up to i coins.