Zombi xəzinə sandığı#3085
Bəzi cəsur döyüşçülər itmiş bir kəndə gəldilər. Onlar çoxlu xəzinələr və böyük bir xəzinə sandığı tapdıqları üçün çox şanslı idilər, lakin həm də qəzəbli zombilərlə qarşılaşdılar.
Döyüşçülər o qədər cəsur idilər ki, zombiləri məğlub edib bütün xəzinələri götürməyə qərar verdilər. Səhərdən axşama qədər davam edən uzun və çətin döyüşdən sonra döyüşçülər başa düşdülər ki, zombilər ölməz və məğlubedilməzdirlər.
Əlbəttə, xəzinənin burada qalması düzgün olmazdı. Təəssüf ki, döyüşçülər sandığın tutumu məhdud olduğuna görə bütün xəzinələri aparıb apara bilməzlər. Yalnız iki növ xəzinə var: zümrüdlər və safirlər. Bütün zümrüdlərin ölçüsü və dəyəri eynidir və sonsuz miqdarda mövcuddur. Eyni şey safirlər üçün də keçərlidir.
Möcüzəli bir artefakta—kompüterə—sahib olan döyüşçülərin kahini kimi və sandığın tutumunu, həmçinin hər növ daşın ölçüsü və dəyərini bildiyiniz üçün, döyüşçülərin sandıqla aparacaqları xəzinələrin maksimal dəyərini hesablamalısınız.
Birinci sətirdə testlərin sayı (t \leq 200) verilir. Hər test ayrı-ayrı sətrlərdə olmaqla, beş tam ədəd , s_1, v_1, s_2, v_2 verilmişdir, burada sandığın tutumu, s_1 və v_1 bir zümrüdün ölçüsü və dəyəri, s_2 və v_2 bir safirin ölçüsü və dəyəridir. Bütün qiymətlər müsbət tam ədədlərdir və -bit imzalı tam ədədə yerləşir.
Hər test üçün bir sətirdə sandıqla aparıla bilən xəzinələrin maksimal dəyərini çap edin.
Nümunə 1