/* $Id$ */

/*

"Offerte speciali" (IOI 1995)
Copyright (C) 2000 Massimo Santini

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

*/

#include <stdio.h>
#include <stdlib.h>

#include "pack.h"

#define MAXOBJECTS 5
#define MAXOFFERS  99
#define MAXCODES   999

fieldpack amount, offer[MAXOFFERS+MAXOBJECTS];
int price[MAXOFFERS+MAXOBJECTS],
	objects,
	offers,
	maxprice;

#define MAXSOLS  3125 /* pari a 5^5 */
#define MAXPRICE 7000

int nsol[MAXPRICE], bestprice;
fieldpack sol[MAXPRICE][MAXSOLS];

void input( void )
{
	int i, j;
	int n, c, obj[MAXCODES];
	fields o, t;
	FILE *in;
	
	for ( i = 0; i < MAXCODES; i++ ) obj[i] = -1;

	/* legge INPUT.TXT registrando il prezzo e la quantità degli
	   oggetti da acquistare, nonche' introduendo una offerta fittizia
	   comprendente un solo oggetto con il suo prezzo. */

	if ( (in = fopen( "INPUT.TXT", "r" ))==NULL ) {
		fprintf( stderr, "non trovo il file INPUT.TXT\n" );
		exit( EXIT_FAILURE );
	}

	fscanf( in, "%d", &objects );

	maxprice = 0;
	cleanfields( o );
	for ( i = 0; i < objects; i++ ) {
		fscanf( in, "%d", &c );
		fscanf( in, "%hd", &(o[i]) );
		fscanf( in, "%d", &(price[i]) );
		
		obj[c] = i;

		cleanfields( t );
		t[i] = 1;
		packfields( &(offer[i]), t );

		maxprice += o[i] * price[i];
	}
	packfields( &amount, o );

	fclose( in );

	/* legge OFFER.TXT e registra la composizione ed il prezzo delle
       offerte */

	if ( (in = fopen( "OFFER.TXT", "r" ))==NULL ) {
		fprintf( stderr, "non trovo il file OFFER.TXT\n" );
		exit( EXIT_FAILURE );
	}

	fscanf( in, "%d", &offers );

	for ( i = 0; i < offers; i++ ) {
		cleanfields( o );
		fscanf( in, "%d", &n );
		for ( j = 0; j < n; j++ ) {
			fscanf( in, "%d", &c );
			fscanf( in, "%hd", &(o[ obj[c] ]) );
		}
		packfields( &(offer[objects + i]), o );
		fscanf( in, "%d", &(price[objects + i]) );
	}
	offers += objects;
	
	fclose( in );
}

void print( void )
{
	int i, j;
	fields x;
	
	unpackfields( x, amount );
	for ( i = 0; i < objects; i++ )
		printf( "object %d, amount %d\n", i, x[i] );
	
	for ( i = 0; i < offers; i++ ) {
		unpackfields( x, offer[i] );
		printf( "offer %d: composition ", i );
		for ( j = 0; j < objects; j++ ) printf( "%d ", x[j] );
		printf( "; price %d\n", price[i] );
	}
}

void addsol( int p, int o )
{
	int i;

	if ( o == amount ) 
		bestprice = p; 
	else if ( isleq( o, amount ) ) { /* non aggiunge se supera */
		/* aggiunge senza duplicare */ 
		sol[p][nsol[p]] = o;
		for ( i = 0; sol[p][i] != o ; i++ );
		if ( i == nsol[p] ) nsol[p]++;
	}
}

void printoffer( fieldpack o )
{
	fields x;
	int i;
	
	unpackfields( x, o );
	for ( i = 0; i < objects ; i++ ) 
		printf( "%d ", x[i] );
	printf( "\n" );
}

void printsol( int p )
{
	int i;

	printf( "solutions for price %d:\n", p );
	for ( i = 0; i < nsol[p]; i++ )
		printoffer( sol[p][i] );
}

void search( void )
{
	int p, i, j, k;

	bestprice = 0;

	for ( p = 1; p <= maxprice && !bestprice; p++ ) {

		/* se c'e` un'offerta pari al prezzo corrente, aggiungila alle sol */
		for ( i = 0; i < offers && !bestprice; i++ ) 
			if ( price[i] == p ) addsol( p, offer[i] );

		/* scomponi il prezzo corrente come k+(p-k) per k = 1..p/2 */
		for ( k = 1; k <= p/2 && !bestprice; k++ ) 
			for ( i = 0; i < nsol[k] && !bestprice; i++ )
				for ( j = 0; j < nsol[p-k] && !bestprice; j++ )
					addsol( p, sol[k][i] + sol[p-k][j] );

		if ( DEBUG ) printf( "price %d nsol %d\n", p, nsol[p] );
	}
	
	printf( "%d\n", bestprice );
}

int main( void ) 
{
	input();
	search();
	
	return 0;
}