2008/2009 SOUTHERN CALIFORNIA REGIONAL
ACM INTERNATIONAL COLLEGIATE PROGRAMMING CONTEST

Problem 8
Android Programming Contest

Thanks in large part to the success of Mr. Data as an officer in Star Fleet, the International Collegiate Programming Contest, in a striking move towards android rights, has established a contest open to teams of androids. Biological entities are allowed to compete, if they dare.
The following paragraph is taken from the official rules for the International Collegiate Programming Contest:
"The total time is the sum of the time consumed for each problem solved. The time consumed for a solved problem is the time elapsed from the beginning of the contest to the submittal of the first accepted run plus 20 penalty minutes for every previously rejected run for that problem. There is no time consumed for a problem that is not solved."
Quite simply, one element of the optimal strategy is not to have any erroneous submissions, so the androids do not have to worry about the penalty minutes. All that remains is to determine the problems the androids should work on and the order in which they should submit them.
Let's assume perfect knowledge-hey, these androids are good-so that they can make a very good estimate of the development time required for each of the problems. The task is to determine which problems each android should solve, and in what order. The androids realize that their best approach is for each to think independently about different problems rather than having all three work on a single problem. Furthermore, each android types infinitely fast, and does not use the computer terminal while thinking. Hence, up to three problems can be simultaneously in progress at any given time, and it is actually possible for all three androids on a team to submit a problem within the same minute. For the same reason, the number of problems posed is greater than the number posed in the contest for biological entities.
Your team is to write a program that will read the android time estimates for each problem and determine the best score the androids will be able to achieve in terms of number of problems solved and minimum total time.
Input to your program will be a series of contest scenarios, one per line. Each line begins in the first column with the number of problems in a given contest as an integer k, 5 k 15. On the same line, separated by single spaces, are k integers between 1 and 300 inclusive, giving the estimated time required to solve each problem in minutes (starting with problem 1). Note that there are exactly 300 minutes in the contest.
For each contest scenario, your program is to print a line containing the number of problems solved and the optimal score in minutes, separated by a single space. No leading or trailing spaces are to appear on the line.

Sample Input

 9 25 50 100 150 100 100 150 225 300
 10 60 120 99 129 15 150 225 135 50 123
 12 6 60 99 45 135 66 231 63 96 39 50 123


Output for the Sample Input

 8 1450
 9 1473
 11 1452



File translated from TEX by TTH, version 3.77.
On 18 Nov 2008, 22:56.