On fictional islands of Matunga archipelage several different tribes use fictional currency - tung. One tung is a very small amount, so all payments are made with coins of different values. For example, one tribe use coins of 7 and 9 tungs, another - 6, 10 and 11 tungs. Every tribe has at least 2 different coins.
Also every tribe has a shop with remarkable feature: if you find an item N tungs worth, you always can find an item priced N+1 tungs in the same shop.
Your goal is to write the function min_price(coins) which finds out the minimum price of item which can be in sale in Matunga tribe shop, knowing the values of coins used there.
Function should return -1 if result is not accessible (i.e. coins of these values can't cover natural row from N to infinity without gaps).
For example, some tribe has coins of 3 and 5 tungs. They can't sell items of 4 or 7 tungs, because 4 and 7 can't be represented as a sum of 3's and 5's. But starting from 8 tungs you can do it with every sum: 8 is 5+3, 9 is 3+3+3, 10 is 5+5, 11 is 5+3+3 and so on. So the answer for this set of coins is 8.
from math import gcd as builtin_gcd
 
"""
This problem could be seen as finding the Frobenius number
Algorithm used
https://brg.a2hosted.com/?page_id=563
based on
The Money Changing Problem Revisited: Computing the Frobenius Number in Time O(ka1), by Sebastian Bocker and Zsuzsanna Liptak, June 2004, Technical Report number 2004-2, University of Bielefeld, Technical Faculty.

"""    
    
def gcd(a, *r):
  for b in r:
    a = builtin_gcd(a, b)
  return a
 
def lcm(a, *r):
  for b in r:
    a *= b // builtin_gcd(a, b)
  return abs(a)
 
def frobenius_number(a):
  def __residue_table(a):
    n = [0] + [None] * (a[0] - 1)
    for i in range(1, len(a)):
      d = gcd(a[0], a[i])
      for r in range(d):
        try:
          nn = min(n[q] for q in range(r, a[0], d) if n[q] is not None)
        except ValueError:
          continue
        if nn is not None:
          for c in range(a[0] // d):
            nn += a[i]
            p = nn % a[0]
            nn = min(nn, n[p]) if n[p] is not None else nn
            n[p] = nn
    return n
 
  
  if len(a) < 2 or gcd(*a) > 1:
    return -1
  return max(__residue_table(sorted(a))) - min(a)

def min_price(a):
    if 1 in a:
        return 1
    else :
        fn = frobenius_number(a) 
        return fn + 1 if not fn == -1 else fn
from math import gcd as builtin_gcd
 
"""
This problem could be seen as finding the Frobenius number
Algorithm used
https://brg.a2hosted.com/?page_id=563
based on
The Money Changing Problem Revisited: Computing the Frobenius Number in Time O(ka1), by Sebastian Bocker and Zsuzsanna Liptak, June 2004, Technical Report number 2004-2, University of Bielefeld, Technical Faculty.

"""    
    
def gcd(a, *r):
  for b in r:
    a = builtin_gcd(a, b)
  return a
 
def lcm(a, *r):
  for b in r:
    a *= b // builtin_gcd(a, b)
  return abs(a)
 
def frobenius_number(a):
  def __residue_table(a):
    n = [0] + [None] * (a[0] - 1)
    for i in range(1, len(a)):
      d = gcd(a[0], a[i])
      for r in range(d):
        try:
          nn = min(n[q] for q in range(r, a[0], d) if n[q] is not None)
        except ValueError:
          continue
        if nn is not None:
          for c in range(a[0] // d):
            nn += a[i]
            p = nn % a[0]
            nn = min(nn, n[p]) if n[p] is not None else nn
            n[p] = nn
    return n
 
  
  if len(a) < 2 or gcd(*a) > 1:
    return -1
  return max(__residue_table(sorted(a))) - min(a)

def min_price(a):
    if 1 in a:
        return 1
    else :
        fn = frobenius_number(a) 
        return fn + 1 if not fn == -1 else fn