DWITE Online Computer Programming Contest, February 2006, Problem 2

Over the course of approximately 35 years, floppy disks have evolved from ~8~ inches in size down to ~3\frac{1}{2}~ inches. Their storage capacity ranged from ~80~ kilobytes (KB) to ~240~ megabytes (MB). Most recently they are becoming extinct, with floppy disk drives being an optional accessory with the purchase of a new computer.

One of the more commonly used floppy disks during its time, was the ~3\frac{1}{2}~-inch ~1.44~ MB capacity disk.

Your job in this problem is to put files onto the ~3\frac{1}{2}~-inch ~1.44~ MB capacity disk so that there is the minimum amount of unused space left on the floppy disk.

The input will contain five sets of data. Each set begins with an integer ~N~, the number of files available to go onto the floppy disk, ~1 \le N \le 25~. The next ~N~ lines, for each set, will contain an integer ~S~, the size in kilobytes (KB) of each of the files, ~1 \le S \le 1\,440~.

The output will contain five lines of data. Each line will contain the minimum amount of unused space left on the floppy disk.

Sample Input (3 sets of data only)

5
1000
500
100
150
400
6
500
233
650
75
22
875
4
235
578
900
599

Sample Output

40
35
28

Sample Input Analysis

In the first set, the files with sizes ~1\,000~ and ~400~ use up the most storage space on the diskette.
In the second set, the files with sizes ~650~, ~500~, ~233~ and ~22~ use up the most storage space on the diskette.
In the third set, the files with sizes ~599~, ~578~ and ~235~ use up the most storage space on the diskette.