Find smallest N for 5-and-21 sums

You are given two positive integers: 5 and 21. We say a positive integer x is representable if it can be written in the form

$x = 5a + 21b$

for some non‑negative integers a and b (i.e., using any number of 5s and 21s, order does not matter).

For example, 99 is representable because:

• 99 = 21 + 21 + 21 + 21 + 5 + 5 + 5.

Find the smallest integer N such that every integer greater than or equal to N is representable.

Output this minimal value of N.

Smallest N where every integer is a sum of two coin denominations

You are given two positive integers p and q. A positive integer x is representable if it can be written as

x = p*a + q*b

for some non-negative integers a and b (any number of ps and any number of qs, order does not matter).

For example, with p = 5 and q = 21, the value 99 is representable because 99 = 21+21+21+21+5+5+5.

Return the smallest integer N such that every integer greater than or equal to N is representable.

Special cases:

• If p and q share a common factor greater than 1, only multiples of that factor are ever representable, so no finite N can cover every integer at or above it — return -1.
• If either denomination is 1, every non-negative integer is representable, so return 0.

The original interview question is the concrete instance p = 5, q = 21, whose answer is 80. This is the Frobenius / Chicken McNugget problem: for coprime p and q the largest non-representable integer is p*q - p - q, so N = p*q - p - q + 1.

Constraints

• 1 <= p, q <= 10000
• p and q are positive integers
• Return -1 when gcd(p, q) > 1 (no finite N exists)
• Return 0 when either p or q equals 1

Examples

Example 1

Input: (5, 21)
Output: 80

Explanation: The original interview instance. Coprime, so N = 5*21 - 5 - 21 + 1 = 80; 79 is the largest value that cannot be written as 5a + 21b.

Example 2

Input: (3, 5)
Output: 8

Explanation: Largest non-representable value is 3*5 - 3 - 5 = 7 (you cannot make 7 from 3s and 5s), so every integer >= 8 is representable.

Hints

1. This is the Frobenius (Chicken McNugget) problem. The answer N is one more than the largest integer that CANNOT be written as pa + qb.
2. If p and q share a common factor > 1, only multiples of that factor are representable, so no finite N exists — handle that case separately.
3. For coprime p and q there is a closed form: the largest non-representable integer is pq - p - q, so N = pq - p - q + 1. You can also compute it with a DP reachability scan up to p*q.
4. A simple verification: build a boolean array reachable[0..p*q], mark reachable[x] true if reachable[x-p] or reachable[x-q] is true, then N is the index after the last false.