{

"Offerte speciali" (IOI 1995)
Copyright (C) 2000 Paolo Boldi

This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

}

program Ioi9512;

{$R+}

const maxprod=5;
      maxoff=99;
      maxvett=7775;
      nomefinput='input.txt';
      nomefofferte='offer.txt';
      nomefout='output.txt';

type vett=array [1..maxprod] of longint; (* Array che rappresenta oggetti da acquistare *)

const zero: vett=(0,0,0,0,0);
      uno: array [1..maxprod] of vett=
           ((1,0,0,0,0),(0,1,0,0,0),(0,0,1,0,0),(0,0,0,1,0),(0,0,0,0,1));
      DEBUG=false;

var
   nprod: byte; (* Numero di tipi di prodotti nel basket *)
   cod: vett; (* Codici prodotti da acquistare *)
   qt: vett; (* Quantit… prodotti da acquistare *)
   b: vett;  (* E' a 0 fino a nprod-1, e infinito dopo *)
   noff: byte; (* Numero offerte *)
   off: array [1..maxprod+maxoff] of (* Array offerte: si considerano
                                  offerte anche i singoletti... *)
              record
                     v: vett; (* Vettore offerta *)
                     c: longint; (* Prezzo offerta *)
              end;
   cmin: array [0..maxvett] of longint; (* Costo minimo per il vettore specificato *)


function min(a,b: longint): longint;
begin
     if (a<b) then min:=a else min:=b
end;

function max(a,b: longint): longint;
begin
     if (a>b) then max:=a else max:=b
end;

function ind(a,b: vett): integer;
(* Se il vettore a e' >= b (componente per componente), calcola il vettore
   a-b e lo interpreta come numero in base 6, restituendone il valore.
   Notate che al massimo pu• essere 55555=100000-1=6^5-1=7775.
   Se il vettore a non e' >= b restituisce -1 *)
var v: integer;
    i: byte;
begin
     v:=0;
     for i:=1 to maxprod do
         if (a[i]>=b[i]) then
            v:=6*v+a[i]-b[i]
         else
             begin
                  v:=-1;
                  break
             end;
     ind:=v
end;

procedure leggiinput;
(* Legge il file input.txt, e si preoccupa di inserire nell'array
   off le offerte relative ai "singoli prodotti" *)
var f: text;
    i: byte;
    p: longint;
begin
     noff:=0;
     assign(f,nomefinput);
     reset(f);
     readln(f,nprod);
     for i:=1 to nprod do
         begin
              readln(f,cod[i],qt[i],p);
              b[i]:=0;
              noff:=noff+1;
              off[noff].v:=uno[i];
              off[noff].c:=p
         end;
     for i:=nprod+1 to maxprod do qt[i]:=0;
     for i:=max(nprod,1) to maxprod do b[i]:=high(longint);
     close(f)
end;

procedure leggioff;
(* Legge le offerte dal file di offerte. Inserisce solo quelle che si riferiscono
   ai soli prodotti che ci interessano, e solo nelle quantita' che ci
   interessano *)
label continua;
var f: text;
    n,np,ip,i,j: byte;
    cp,qp: longint;
    v: vett;

    function cerca(c: longint): byte;
    (* Guarda se c Š uno dei codici presenti in cod[1..nprod]; se sŤ, ne
       restituisce l'indice, altrimenti restituisce 0 *)
    var i,t: byte;
    begin
         t:=0;
         for i:=1 to nprod do
             if (cod[i]=c) then t:=i;
         cerca:=t
    end;

begin
     assign(f,nomefofferte);
     reset(f);
     readln(f,n);
     for i:=1 to n do
         begin
              for j:=1 to maxprod do v[j]:=0;
              read(f,np);
              for j:=1 to np do
                  begin
                       read(f,cp,qp); (* Codice/quantita' prodotto *)
                       ip:=cerca(cp); (* Cerca codice prodotto *)
                       if (ip=0) or (qt[ip]<qp) then goto continua;
                       v[ip]:=qp
                  end;
              noff:=noff+1;
              off[noff].v:=v;
              readln(f,off[noff].c);
              continua:
         end;
     close(f)
end;

procedure cercacostomin;
var a: vett;
    i: byte;
    t,offi: longint;
    v: integer;
begin
     (* I cicli for servono per generare tutti i vettori della forma
        a_1...a_5 dove a_i<=qt_i (e a_i=0 se i>nprod), in ordine crescente
        di a_1+...+a_5. Per farlo, osserviamo che il massimo raggiungibile
        per ciascun indice e' il minimo fra qt_i e quanto manca ancora per
        arrivare alla somma desiderata; l'indice minimo deve essere normalmente
        0, tranne che da nprod (compreso) in poi, dove l'indice minimo e
        l'indice massimo devono coincidere (questo e' il motivo per cui
        si usa il vettore addizionale b)
     *)
     for t:=1 to qt[1]+qt[2]+qt[3]+qt[4]+qt[5] do
     for a[1]:=0 to min(qt[1],t) do
     for a[2]:=min(b[2],t-a[1]) to min(qt[2],t-a[1]) do
     for a[3]:=min(b[3],t-a[1]-a[2]) to min(qt[3],t-a[1]-a[2]) do
     for a[4]:=min(b[4],t-a[1]-a[2]-a[3]) to min(qt[4],t-a[1]-a[2]-a[3]) do
     for a[5]:=min(b[5],t-a[1]-a[2]-a[3]-a[4]) to min(qt[5],t-a[1]-a[2]-a[3]-a[4]) do
         begin
              if (DEBUG) then
                 begin
                      for i:=1 to maxprod do
                          write(a[i],' ');
                      writeln;
                      readln
                 end;
              (* Determina il modo ottimale per ottenere il vettore a
                 togliendo in tutti i modi possibili un'offerta e considerando
                 l'ottimo gia' calcolato per ottenere il vettore risultante *)
              offi:=high(longint);
              for i:=1 to noff do
                  begin
                       v:=ind(a,off[i].v);
                       if (v>=0) and (off[i].c+cmin[v]<offi) then
                          offi:=off[i].c+cmin[v]
                  end;
              cmin[ind(a,zero)]:=offi;
              if (DEBUG) then
                 writeln(offi)
         end
end;

procedure output;
(* Produce l'output *)
var f: text;
begin
     assign(f,nomefout);
     rewrite(f);
     writeln(f,cmin[ind(qt,zero)]);
     close(f)
end;

begin
     leggiinput;
     leggioff;
     cercacostomin;
     output
end.