Knapsack - Рюкзак

Just Enough Space

After a PR mishap with a former employee, the NSA might need to increase storage in one of their datacenters: the Russian and Spanish translators have a backlog, and the captured phone conversations need to be stored in the meantime. Up to 1 exabyte of data needs to be stored. Unfortunately, there is currently no extra storage available at all.

Due to budget limitations, it is not possible to immediately buy new disks, and the system administrator (you) wants to solve this by reducing the data redundancy. For performance and reliability, all data is currently on large RAID-1 sets of four disks in each server. More data can be stored by converting some of these sets to the slower RAID-5 technique.

Specifically, there are currently n RAID-1 sets. Each set i is built using disks of size Si, and this set can hold Si GB of data. If you convert one set to RAID-5, it can hold three times as much data: 3·Si GB. You want to convert as few GBs of storage as possible.


Disks with size S = 4 capacity respectively 4 GB (D0...D3) and 3·4 = 12 GB (D0...D11).


On the first line one positive number: the number of test cases, at most 100. After that per test case:

  • one line with two space-separated integers n and e (1 n 100 and 0 e 109): the number of RAID-1 sets, and the amount of extra space in GB required, respectively.
  • one line with n space-separated integers S1...Sn (1 Si2000): the sizes of all raid sets in GB.


For each test case print one line with an integer: the number of GB you need to convert, or the string "FULL" if not enough diskspace can be freed.


  • In the first example, it is enough to convert one RAID-set: the new capacity is then 1500 + 500 = 2000 GB.
  • In the second example, converting the 600 GB and 700 GB disks will increase the storage from 400 + 600 + 700 + 1000 = 2700 GB to 400 + 1800 + 2100 + 1000 = 5300 GB, enough to store the extra 2400 GB of data. All other conversions are less efficient.
  • In the third example there is no way to come up with the required amount of free disk space.
    Time limit 1 second
    Memory limit 64 MiB
    Input example
    2 500
    500 500
    4 2400
    400 600 700 1000
    2 1000
    10 10
    Output example
    Source 2013 Benelux Algorithm Programming Contest (BAPC), Preliminaries, September 28, Problem J