Freeing Up Capacity

The NSA keeps piling up Russian and Spanish translation data and wiretap recordings, so it wants to grow its data center to one exabyte.

The budget is thin and no new disks can be bought. The capacity has to come from changing how the existing disks store data.

Every server runs four disks as a RAID-1 set. A RAID-1 set converted to RAID-5 holds three times as much.

The data center has n RAID-1 sets. Set i is built from disks of size $S_i$ and holds $S_i$ GB of data. After conversion to RAID-5 the same set holds $3 S_i$ GB, so converting set i raises the total capacity by $2 S_i$ GB.

Write a program that picks the sets to convert so the data center gains at least e GB more capacity, while the total size of the converted sets stays as small as possible.

For example, with disk size $S = 4$ a RAID-1 set stores 4 GB ($D_0$ through $D_3$) and a RAID-5 set stores $3 \times 4 = 12$ GB ($D_0$ through $D_{11}$).

The first line has the number of test cases, which is at most 100.

The first line of each test case has the number of RAID-1 sets n and the capacity e that has to be gained. ($1 \le n \le 100$, $0 \le e \le 10^9$)

The second line has the sizes of the sets, $S_1$ through $S_n$. ($1 \le S_i \le 2000$)

For each test case, print on one line the smallest capacity in GB that has to be converted. If no choice of sets gains e GB more capacity, print FULL.

• The first case of the example needs a single set converted. The total capacity becomes 1500 + 500 = 2000 GB.
• The second case converts the 600 GB set and the 700 GB set, turning 400 + 600 + 700 + 1000 = 2700 GB into 400 + 1800 + 2100 + 1000 = 5300 GB. Every other combination converts more.
• The third case cannot reach the required capacity.