#! /usr/bin/perl

use strict;
use warnings;

my @all;

use Memoize;

memoize('breakup');

print largest(@ARGV)."\n";

sub largest
{
  my $small = shift;
  my %need;

  @all = reverse @_;

  my $highest = 0;

  for my $m_target (1..($small-1))
  {
    # find the smallest number ($target) which can be made from the in
+put
    # numbers and which gives remainder $m_target when divided by $sma
+ll.

    my $target = $m_target;
    while ($target += $small)
    {
      if (0) # change to 1 to see details
      {
        my @b = breakup($target, 0);
        nice($target, @b);
      }
      last if breakup($target, 0);
    }
    $target -= $small;
    print  "$target == $m_target (mod $small)\n";
    $highest = $target if $highest < $target;
  }
  return $highest;
}

sub nice
{
  my $target = shift;
  print "---------------\n\ntarget = $target\n";
  foreach my $sol (@_)
  {
    print join(", ", @$sol)."\n";
  }
}

sub breakup
{
  my ($target, $sub) = @_;
#  $count++;

  my $cur = $all[$sub];

  my @solns;
  if ($target == $cur)   
  {
    push(@solns, [$cur]);
  }
   
  if ($target >= $cur)
  {
    push(@solns, map {[$cur, @$_]} (breakup($target - $cur, $sub)));
  }

  push(@solns, breakup($target, $sub + 1)) unless ($sub == $#all);
 
  return @solns;
}
[download]