Ya que los límites nos lo permiten, emplearemos un algoritmo de BRUTE FORCE para resolver el problema. Para resolverlo empleamos un algoritmo que nos "cuente" números de N cifras tal que en cada lugar (donde va un dígito) tenga un "Tope" diferente. Por ejemplo, si tenemos 2 tipos de monedas con 2 4 de existencia entonces queremos ver todos los números de la siguente forma: 00, 10, 20, 01, 11, 21, 02, 12, 22, 03, 13, 23, 04, 14, 24. Si que realizamos todas las combinaciones en el caso extremo, lo que quiere decir que haremos 9⁸ = 3¹⁶ combinaciones posibles el cual es un número todavía suficientemente razonable para procesar (en una computadora rápida je).

Empleamos un arreglo de "Tope" que nos indica en cada posición hasta que número podemos llegar. Un arreglo en donde tenemos el número que se ha calculado.

El código en lenguaje C++ quedaría como el siguiente:

#include <stdio.h>
//---------------------------------------------------------------------------
FILE *Input,*Output;
int *CostoMoneda,SumaTotal,Mitad,Minimo;
///******************************
int Absoluto(int X)
{
if( X < 0 ) { return -X; }

return X;
}
///******************************
// 
void Checa(int N,int *Array)
{
int Temp,Suma,i;

Suma = 0;
for(i = 0; i < N; i++)
  { Suma += Array[i]*CostoMoneda[i]; }

Temp = Absoluto(2*Suma-SumaTotal);
if( Temp < Minimo )
  {
  Minimo = Temp;
  Mitad = Suma;
  }
}
///******************************
// Generamos los numeros de base variable.
void CuentaBaseVariable(int N,int *Tope)
{
// Inicializamos las variables que emplearemos
int i,Pos;
int *Array = new int[N+1];

// Comenzamos con el número de N + 1 ceros
for(i = 0; i < N; i++)
  { Array[i] = 0; }

// Pos nos indica en qué cifra estamos.
// Si Pos == N entonces quiere decir que ya contamos 
// todos los números
Pos = 0;
while( Pos < N )
  {
  // Mandamos a checar el número
  Checa(N,Array);
  
  // Sumamos uno a la primera cifra.
  Pos = 0;
  Array[Pos]++;
  
  // Si la cifra (Array[Pos]) en la posición Pos es igual a Tope[Pos]
  // entonces hacemos cero esa cifra y aumentamos en uno a la 
  // siguiente cifra y recorremos Pos en uno.
  while( Pos < N && Array[Pos] == Tope[Pos] )
    {
    Array[Pos] = 0;
    Pos++;
    Array[Pos]++;
    }
  }
  
// Liberamos la memoria.  
delete[] Array;
}
///******************************
int main(void)
{
int i,N,*Tope;
Input = fopen("Input.txt","r+t");

Minimo = 36000;
SumaTotal = 0;

fscanf(Input,"%d",&N);

Tope = new int[N];
CostoMoneda = new int[N];

for(i = 0; i < N; i++)
  {
  fscanf(Input,"%d",&Tope[i]);
  Tope[i]++;
  }
  
for(i = 0; i < N; i++)
  {
  fscanf(Input,"%d",&CostoMoneda[i]);
  SumaTotal += ((Tope[i]-1)*CostoMoneda[i]);
  }

fclose(Input);

CuentaBaseVariable(N,Tope);

Output = fopen("Output.txt","w+t");

fprintf(Output,"%d %d",Mitad,SumaTotal-Mitad);

fclose(Output);


        return 0;
}