#!/usr/bin/perl -w

use v5.16;
use Data::Dumper;
use List::Util qw(any);

my %rules;
while (<>) {
	chomp;
	my ($srcs, $dstcount, $dst) = /(.*) => (\d+) (\w+)/;
	my %srcs = reverse $srcs =~ /(\d+) (\w+)/g;
	$rules{$dst} = {
		count => $dstcount,
		srcs  => \%srcs,
	};
}

use List::Util qw(first);

sub fuel_from_ore {
	my $fuel = shift;

	my (%want, %have);
	$want{FUEL} = $fuel;
	while (my $w = first { $_ ne 'ORE' && $want{$_} } keys %want) {
		my $r = $rules{$w};
		my $rcount = int (($want{$w}+$r->{count}-1)/$r->{count});
		# say "want $want{$w} of $w, rule has $r->{count}, need $rcount rules";
		if ($rcount * $r->{count} > $want{$w}) {
			$have{$w} = $rcount * $r->{count} - $want{$w};
		}
		delete $want{$w};
		for my $src (keys %{ $r->{srcs} }) {
			my $need = $r->{srcs}->{$src} * $rcount;
			if ($have{$src}) {
				if ($need >= $have{$src}) {
					$need -= $have{$src};
					delete $have{$src};
				} else {
					$have{$src} -= $need;
					next;
				}
			}
			$want{$src} += $need;
		}
		# say "want: ", join(', ', map { "$want{$_} of $_" } keys %want);
		# say "have: ", join(', ', map { "$have{$_} of $_" } keys %have);
		# say "";
	}
	return $want{ORE};
}

my $low = fuel_from_ore(1);
say $low;
my $high = $low;

my $max_ore = 1_000_000_000_000;
$high *= 2 while fuel_from_ore($high) <= $max_ore;

my $now;
do {
	$now = int(($high + $low) / 2);
	if (fuel_from_ore($now) <= $max_ore) {
		$low = $now;
	} else {
		$high = $now;
	}
} while ($low + 1 < $high);

say $low;
