use strict;
use warnings;
use Test::More 'no_plan';

$| = 1;

my %cache;

sub exact {
    my ($amount, @bills) = @_;
    return $cache{$amount} if defined $cache{$amount};
    return 1 if !$amount;
    return 0 if  $amount < 0;
    foreach my $bill (@bills) {
        return $cache{$amount} = 1 if exact($amount - $bill, @bills)
    }
    return $cache{$amount} = 0;
}

sub largest {
    %cache = ();
    my @bills    = @_;
    my $smallest = $bills [0];
    return -1 if $smallest == 1;
    my $start = 0;
    my $prev  = 0;
    for (my $t = 1; 1; $t++) {
        if (exact($t, @bills)) {
            if ($prev) {
                if ($t - $start + 1 == $smallest) {return $start - 1}
            }
            else {$start = $t}
            $prev = 1;
        }
        else {
            $prev = 0;
        }
    }
}

is (largest(6,9,20),                            43);
is (largest(3,5),                                7);
is (largest(6,11,20),                           27);  
is (largest(17,18,19,20),                      101);
is (largest(2,3,5,10),                           1);
is (largest(1000,1001,1002,1003,1004,1005), 199999);
        
__END__
ok 1
ok 2
ok 3
ok 4
ok 5
ok 6
1..6
[download]