eolymp
bolt
Try our new interface for solving problems
Problems

Just Enough Space

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 \textbf{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 \textbf{n} RAID-1 sets. Each set \textbf{i} is built using disks of size \textbf{S_i}, and this set can hold \textbf{S_i} GB of data. If you convert one set to RAID-5, it can hold three times as much data: \textbf{3·S_i} GB. You want to convert as few GBs of storage as possible. \includegraphics{https://static.e-olymp.com/content/50/501e11be89afb610b7cebfe4c1544fa2f4668512.jpg} Disks with size \textbf{S }= \textbf{4 }capacity respectively \textbf{4 }GB (\textbf{D0...D3}) and \textbf{3·4} = \textbf{12} GB (\textbf{D0...D11}). \InputFile On the first line one positive number: the number of test cases, at most \textbf{100}. After that per test case: \begin{itemize} \item one line with two space-separated integers \textbf{n }and \textbf{e }(\textbf{1 }≤ \textbf{n }≤ \textbf{100} and \textbf{0 }≤ \textbf{e }≤ \textbf{10^9}): the number of RAID-1 sets, and the amount of extra space in GB required, respectively. \item one line with \textbf{n} space-separated integers \textbf{S_1...S_n} (\textbf{1 }≤ \textbf{S_i} ≤ \textbf{2000}): the sizes of all raid sets in GB. \end{itemize} \OutputFile For each test case print one line with an integer: the number of GB you need to convert, or the string "\textbf{FULL}" if not enough diskspace can be freed. \Note \begin{itemize} \item In the first example, it is enough to convert one RAID-set: the new capacity is then \textbf{1500 + 500 }= \textbf{2000 }GB. \item In the second example, converting the \textbf{600 }GB and \textbf{700 }GB disks will increase the storage from\textbf{ 400 + 600 + 700 + 1000} = \textbf{2700} GB to \textbf{400 + 1800 + 2100 + 1000} = \textbf{5300 }GB, enough to store the extra \textbf{2400 }GB of data. All other conversions are less efficient. \item In the third example there is no way to come up with the required amount of free disk space. \end{itemize}
Time limit 1 second
Memory limit 64 MiB
Input example #1
3
2 500
500 500
4 2400
400 600 700 1000
2 1000
10 10
Output example #1
500
1300
FULL
Source 2013 Benelux Algorithm Programming Contest (BAPC), Preliminaries, September 28, Problem J