e-olymp
Змагання

Knapsack - Рюкзак

Достаточно места

После серьезной неудачи с бывшим сотрудником, Агенству Национальной Безопасности потребовалось увеличить хранилища в одном из их центров обработки данных: российские и испанские переводчики не успевают, а перехваченные телефонные разговоры должны записываться немедленно. Необходимо хранить до 1 экзабайта информации. К сожалению, в настоящее время совсем нет дополнительного места для хранения данных.

Из-за ограничений бюджета стало невозможно немедленно покупать новые диски, поэтому системный администратор (Вы) хочет решить эту проблему за счет уменьшения избыточности данных. Для производительности и надежности все данные в настоящее время находятся на крупных RAID-1 наборах из четырех дисков в каждом сервере. Больше данных может быть сохранено путем преобразования некоторых из этих серверов в RAID-5 с более медленным доступом.

Изначально имеется n RAID-1 устройств. Каждое i-ое устройство состоит из дисков размера Si, которые могут содержать Si Гб данных. Если одно такое устройство преобразовать в RAID-5, то оно сможет содержать в три раза больше данных: 3·Si Гб. Необходимо преобразовать как можно меньший объем памяти в Гб.

prb6415

Диски размера S = 4 с объемом 4 GB (D0...D3) и 3·4 = 12 GB (D0...D11).

Входные данные

Первая строка содержит количество тестов, не большее 100. Каждый тест состоит из:

  • строки с двумя целыми числами n и e (1 n 100 и 0 e 109) - количество устройств RAID-1 и количество требуемой дополнительной памяти в Гб.
  • одна строка с n целыми числами S1...Sn (1 Si2000): размеры всех рейд устройств в Гб.

Выходные данные

Для каждого теста вывести в отдельной строке количество Гб которое следует преобразовать, или строку "FULL" если получить указанный объем памяти невозможно.

Замечание

  • В первом примере достаточно преобразовать одно RAID - устройство: новый объем памяти составит 1500 + 500 = 2000 Гб.
  • Во втором примере преобразование 600 Гб и 700 Гб дисков увеличит память с 400 + 600 + 700 + 1000 = 2700 Гб до 400 + 1800 + 2100 + 1000 = 5300 Гб, что будет достаточным для хранения дополнительных 2400 Гб данных. Все остальные преобразования менее эффективны.
  • В третьем примере невозможно поучить дополнительно требуемый объем памяти.
      Ліміт часу 1 секунда
      Ліміт використання пам'яті 64 MiB
      Вхідні дані
      3
      2 500
      500 500
      4 2400
      400 600 700 1000
      2 1000
      10 10
      
      Вихідні дані
      500
      1300
      FULL
      
      Джерело 2013 Benelux Algorithm Programming Contest (BAPC), Preliminaries, Вересень 28, Задача J