sub solution_1 {
    # queue solution
    # O(2*N+M) memory, O(N^2*M) time
    my ($list_ref1, $list_ref2) = @_;
    my @list1;
    my @list2;
    if (@$list_ref1 <= @$list_ref2) {
       @list1 = @$list_ref1;
       @list2 = @$list_ref2;
    } else {
       @list1 = @$list_ref2;
       @list2 = @$list_ref1;
    }
    
    my @queue = ( $list1[-1]+$list2[-1] );
    for my $k (0 .. 2*$#list1) {
        for my $i (0 .. $k) {
            next if $i >= @list1;
            my $j = $k - $i;
            last if $j >= @list2;

            print OUT (shift(@queue),"\n") if @queue >= 0.5*@list1*@list2;

            my $sum = $list1[$i]+$list2[$j];
            my $count = 0;
            $count++ until $sum <= $queue[$count];
            splice @queue, $count, 0, $sum;
        }
    }
    pop @queue;
    print OUT "$_\n" for @queue;
}