Çürük İplər
Tutaq ki, bizdə eyni uzunluqda olan n ədəd kəndir var və bu kəndirləri ağır bir əşyanı qaldırmaq üçün istifadə etmək istəyirik. Hər bir kəndir üçün bir qopma çəkisi t müəyyən edilib, yəni əgər biz həmin kəndirlə t-dən ağır bir əşyanı qaldırmağa çalışsaq, kəndir qopacaq. Lakin biz ağır əşyaya bir neçə kəndir bağlayıb (paralel olaraq) onu bütün bağlanmış kəndirlərlə qaldıra bilərik. k kəndir istifadə edərək çəkisi w olan ağır əşyanı qaldırarkən, hər bir k kəndirin, qopma çəkisindən asılı olmayaraq, w/k çəkisini qaldırdığı qəbul edilir. Lakin, əgər w/k bəzi kəndirin qopma çəkisi t-dən böyükdürsə, həmin kəndir qopacaq.
Məsələn, qopma çəkiləri 1, 10 və 15 olan üç kəndir, hamısı bir əşyaya bağlandıqda, ən zəif olanı qopmadan 3-dən ağır bir əşyanı qaldıra bilməz. Lakin ikinci kəndir tək başına ən çox 10 çəkisi olan bir əşyanı qaldıra bilər.
Verilən kəndirlərin qopma çəkilərinə əsasən, sizin vəzifəniz verilmiş kəndirlərin bir alt qrupunu bağlayaraq heç birinin qopmaması şərti ilə qaldıra biləcək ən ağır əşyanın çəkisini tapmaqdır.
Giriş verilənləri
Giriş faylının ilk sətri t (1 ≤ t ≤ 10) ədəd test halının sayını ehtiva edir, ardınca hər bir test halı üçün giriş məlumatları gəlir. Hər bir test halının ilk sətri kəndirlərin sayını göstərən n (1 ≤ n ≤ 1000) tək tam ədədindən ibarətdir. İlk sətrin ardınca n kəndirin qopma çəkilərini göstərən və boşluqla ayrılmış n ədəd tam ədəd gəlir, bu ədədlər 1 ilə 10000 arasında dəyişir.
Çıxış verilənləri
Çıxış faylının hər sətri müvafiq test halında heç bir kəndirin qopmaması şərti ilə qaldırıla biləcək ən ağır çəkini göstərən tək ədəd olmalıdır.