#include <stdio.h>#include <stdlib.h>#include <string.h>int f[ 52 ][ 22501 ];int h[ 101 ];int main(){ int n,sum; while ( scanf("%d",&n) != EOF && n != -1 ) { sum = 0; for ( int i = 1 ; i <= n ; ++ i ) { scanf("%d",&h[ i ]); sum += h[ i ]; } memset( f, 0, sizeof( f ) ); f[ 0 ][ 0 ] = 1; for ( int i = 1 ; i <= n ; ++ i ) for ( int l = n/2+1 ; l > 0 ; -- l ) for ( int j = sum/2 ; j >= h[ i ] ; -- j ) if ( f[ l-1 ][ j-h[ i ] ] ) f[ l ][ j ] = 1; int move = sum/2; while ( move ) { if ( n%2 == 0 && f[ n/2+0 ][ move ] ) break; if ( n%2 == 1 && f[ n/2+1 ][ move ] ) break; if ( n%2 == 1 && f[ n/2-0 ][ move ] ) break; -- move; } printf("%d %dn",move,sum-move); } return 0;}
