#!/usr/bin/perl

use Math::CDF qw/ pnorm /;

$EPS = 0.0001;

sub kl {
  my ($p,$q) = @_;
  return $p*log($p/$q) + (1-$p)*log((1-$p)/(1-$q));
}

sub rand_err {
  my ($mu, @margins) = @_;
  my $sum = 0;
  for $i (@margins) {
    $sum += pnorm(-1.0*$mu*$i);
  }
  return $sum / $#margins;
} 
  
sub find_eps {
  my ($a,$b) = @_;
  $lower = $upper = $a;
  while(kl($a, $upper) < $b && $upper <= 1-($EPS/2)) { 
    $upper += (1-$upper)/2; 
  }
  if($upper > 1-($EPS/2)) { return 1; }
  while($upper-$lower > $EPS) {
    if(kl($a, $lower + ($upper-$lower)/2) > $b) {
      $upper = $lower + ($upper-$lower)/2;
    } else {
      $lower = $lower + ($upper-$lower)/2;
    }
  }
  return $upper;
}

$delta = $ARGV[2];

open(IN, $ARGV[0]);
while(<IN>) {
  ($a,$b) = split;
  push @margins, $b;
}
close(IN);

open(IN, $ARGV[1]);
for ($i = 0; $i <= $#margins; $i++) {
  $line = <IN>;
  chomp($line);
  $margins[$i] *= $line;
}
close(IN);

$n = $#margins+1;

for ($mu=0.01; $mu <= 100.0; $mu += 0.1) {
  push @mus, $mu;
}

for $mu (@mus) {
  $kl_upper = ($mu*$mu/2 + log(($n+2)/$delta))/($n+1);
  $err = rand_err($mu, @margins);
  $bound{$mu} = find_eps($err, $kl_upper);
}

$best_mu = $mus[0];
for $mu (@mus) {
  if($bound{$mu} < $bound{$best_mu}) {
    $best_mu = $mu;
  }
}

print($bound{$best_mu} . " " . $best_mu);
