#!/usr/bin/perl
use strict;
use warnings;

my (
	@words,
	$catcount,
	$bestscore,
	$bestsolution,
);

# collect words and count categories
$catcount= 0;
while (<DATA>) {
    chomp;
    my($cat, $word)= split;
    push(@{$words[--$cat]}, $word);
	$catcount= $cat if $cat>$catcount;
}

# initialise solution
$bestscore= 0;
$bestsolution= '';

find_best_solution($catcount+1, '');

print "\n",$bestsolution;

sub find_best_solution {
	my($cat, $solution)= @_;
	if ($cat > 0) {
		# Still categories to check
		--$cat;
		foreach (@{$words[$cat]}) {
			find_best_solution($cat, $_ . "\n".  $solution);
		}
	}
	else {
		# All categories done
		my $score= score($solution);
		if ($score > $bestscore) {
			print STDERR "\rNew best score: ",$score;
			$bestscore= $score;
			$bestsolution= $solution;
		}
#		else { #decomment if you want to see it work
#			print STDERR " (",$score,")",("\010" x (3+length($score)));
#		}
	}
}

# Scoring is done for the concatenation of the words
sub score {
	# Get the words and lowercase them 
    local($_)= lc shift;
	# being paranoid I remove all non-letters
    s/[^a-z]//g;
    my $score= 0;
    while ($_) {
		# get the first character (alternative substr($_,0,1);)
        my $f=chr(ord($_));
		# count that character and remove it
        my $n=s/$f//g;
		# add the score 1+2+3+4..+n= n*(n+1)/2
        $score+= ($n+1)*$n/2;
    }
    return $score;
}

__DATA__
1 alabama
1 arkansas
1 alaska
1 delaware
1 hawaii
1 indiana
1 kansas
1 montana
1 delaware
2 sazerac
2 sangrita
3 radiator
3 gastank
3 engine
3 heater
3 fender
3 wheel
3 detent
3 battery
3 clutch
3 mirror
3 window
4 alloy
4 amalgam
4 vanadium
4 copper
4 steel
5 rutabaga
5 limabean
5 cress
5 carrot
5 sorrel
5 squash
5 cabbage
5 pepper
5 lettuce
5 beet
5 leek
5 celery
5 endive
5 rhubarb
5 parsnip
5 pumpkin
6 azalia
6 camellia
6 dahlia
6 gardenia
6 gentian
6 vervain
6 canna
6 hepatica
6 bluebell
6 anemone
6 oleander
7 lasagna
7 macaroni
7 pastina
7 gnocchi
7 tortelli
7 alfabeto
8 mascagni
8 britten
8 menotti
9 unamas
9 tacotime
9 pizzahut
9 tacobell
9 panago
9 tacomayo
9 edojapan
9 hardees
10 caramel
10 marzipan
10 taiglach
10 taffy
10 brittle
10 fondant
10 toffee
10 dragee

##</code><code>##

s$$([},&%#}/&/]+}%&{})*;#$&&s&&$^X.($'^"%]=\&(|?*{%.+=%;.#_}\&"^"-+%*).}%:##%}={~=~:.")&e&&s""`$''`"e