Гнилые верёвки
Представьте, что у вас есть ( n ) верёвок одинаковой длины, и вы хотите использовать их для подъёма тяжёлого объекта. Каждая верёвка имеет разрывное усилие t, то есть, если вы попытаетесь поднять объект, который тяжелее t, используя эту верёвку, она порвётся. Однако, вы можете прикрепить несколько верёвок к объекту (параллельно) и поднять его с помощью всех прикреплённых верёвок. При использовании k верёвок для подъёма объекта весом w, предполагается, что каждая из k верёвок несёт нагрузку w/k. Если w/k превышает t для какой-либо верёвки, она порвётся.
Например, если у вас есть три верёвки с разрывными усилиями 1, 10 и 15, и вы прикрепите все три к объекту, они не смогут поднять объект весом более 3, так как самая слабая верёвка порвётся. Однако вторая верёвка может самостоятельно поднять объект весом до 10.
Зная разрывные усилия n верёвок, ваша задача — определить максимальный вес объекта, который можно поднять, прикрепив подмножество данных верёвок, не порвав ни одну из них.
Входные данные
Первая строка входного файла содержит одно целое число t ((1 t 10)), количество тестов, за которым следуют данные для каждого теста. Первая строка каждого теста содержит одно целое число n ((1 n 1000)), количество верёвок. Следующая строка содержит n целых чисел от 1 до 10000, представляющих разрывные усилия верёвок, разделённых пробелами.
Выходные данные
Каждая строка выходного файла должна содержать одно число, представляющее максимальный вес, который можно поднять в соответствующем тесте, не порвав ни одну из выбранных верёвок.